A practical algorithm for decomposing polygonal domains into convex polygons by diagonals

We present algorithms for decomposing a polygon (with holes) into convex polygons by diagonals. The methods are computationally quick, and although the partitions that they produce may not have minimal cardinality they usually have a low number of convex pieces. Thus, the methods are suitable for being used when achieving a modest load on the CPU time is more important than finding optimal decompositions as, for instance, in location problems. Part of the results in this paper are from Fernández (1999), and were presented in Fernández et al. (1998). This work has been supported by the Ministry of Science and Technology of Spain under the research projects BEC2002-01026, SEJ2005-06273/ECON (J. Fernández, B. Tóth and B. Pelegrín) and TIC2003-05982-C05-03 (L. Cánovas), in part financed by the European Regional Development Fund (ERDF).     

Decomposing a simple polygon into pseudo-triangles and convex polygons

In this paper we consider the problem of decomposing a simple polygon into subpolygons that exclusively use vertices of the given polygon. We allow two types of subpolygons: pseudo-triangles and convex polygons. We call the resulting decomposition PT-convex. We are interested in minimum decompositions, i.e., in decomposing the input polygon into the least number of subpolygons. Allowing subpolygons of one of two types has the potential to reduce the complexity of the resulting decomposition considerably.The problem of decomposing a simple polygon into the least number of convex polygons has been considered. We extend a dynamic-programming algorithm of Keil and Snoeyink for that problem to the case that both convex polygons and pseudo-triangles are allowed. Our algorithm determines such a decomposition in O(n³) time and space, where n is the number of the vertices of the polygon.     

Distances of group tables and latin squares via equilateral triangle dissections

Denote by gdist(p)$\mathrm{gdist}(p)$ the least non-zero number of cells that have to be changed to get a latin square from the table of addition modulo p  . A conjecture of Drápal, Cavenagh and Wanless states that there exists c>0$c>0$ such that gdist(p)?clog(p)$\mathrm{gdist}(p)?c\log (p)$. In this paper the conjecture is proved for c≈7.21$c\approx 7.21$, and as an intermediate result it is shown that an equilateral triangle of side n   can be non-trivially dissected into at most 5_log2(n)$5{\log }_2(n)$ integer-sided equilateral triangles. The paper also presents some evidence which suggests that gdist(p)/log(p)≈3.56$\mathrm{gdist}(p)/\log (p)\approx 3.56$ for large values of p.     

Latin bitrades,dissections of equilateral triangles,and abelian groups

Let T=(T^*, T^?) be a spherical latin bitrade. With each a=(a₁, a₂, a₃)∈T^* associate a set of linear equations Eq(T, a) of the form b₁+b₂=b₃, where b=(b₁, b₂, b₃) runs through T^*\{a}. Assume a₁=0=a₂ and a₃=1. Then Eq(T,a) has in rational numbers a unique solution $b_{i}=\bar{b}_{i}Let T=(T^*, T^?) be a spherical latin bitrade. With each a=(a₁, a₂, a₃)∈T^* associate a set of linear equations Eq(T, a) of the form b₁+b₂=b₃, where b=(b₁, b₂, b₃) runs through T^*\{a}. Assume a₁=0=a₂ and a₃=1. Then Eq(T,a) has in rational numbers a unique solution $b_{i}=\bar{b}_{i}$. Suppose that $\bar{b}_{i}\not= \bar{c}_{i}$ for all b, c∈T^* such that $\bar{b}_{i}\not= \bar{c}_{i}$ and i∈{1, 2, 3}. We prove that then T^? can be interpreted as a dissection of an equilateral triangle. We also consider group modifications of latin bitrades and show that the methods for generating the dissections can be used for a proof that T^* can be embedded into the operational table of a finite abelian group, for every spherical latin bitrade T. © 2009 Wiley Periodicals, Inc. J Combin Designs 18: 1–24, 2010     

Limit shape of convex lattice polygons with minimal perimeter

Let n be a positive integer and · any norm in . Denote by B the unit ball of · and the class of convex lattice polygons with n vertices and least ·-perimeter. We prove that after suitable normalization, all members of tend to a fixed convex body, as n→∞.     

An exact construction of digital convex polygons with minimal diameter

Given a natural number n, an exact formula is derived for the minimal possible size MD(n) of a square grid, in which a digital convex n-gon can be inscribed. An exact construction of a digital convex n-gon which can be inscribed into a square grid of size MD(n) is also given.     

The convex dimension of a graph

The convex dimension of a graph G=(V,E) is the smallest dimension d for which G admits an injective map f:V?R^d of its vertices into d-space, such that the barycenters of the images of the edges of G are in convex position. The strong convex dimension of G is the smallest d for which G admits a map as above such that the images of the vertices of G are also in convex position. In this paper we study the convex and strong convex dimensions of graphs.     

Approximation of convex bodies by axially symmetric bodies

Let be an arbitrary planar convex body. We prove that contains an axially symmetric convex body of area at least . Also approximation by some specific axially symmetric bodies is considered. In particular, we can inscribe a rhombus of area at least in , and we can circumscribe a homothetic rhombus of area at most about . The homothety ratio is at most . Those factors and , as well as the ratio , cannot be improved.

     

Representation of convex geometries by circles on the plane

Convex geometries are closure systems satisfying the anti-exchange axiom. Every finite convex geometry can be embedded into a convex geometry of finitely many points in an $n$-dimensional space equipped with a convex hull operator, by the result of Kashiwabara et al. (2005). Allowing circles rather than points, as was suggested by Czédli (2014), may presumably reduce the dimension for representation. This paper introduces a property, the Weak 2 × 3-Carousel rule, which is satisfied by all convex geometries of circles on the plane, and we show that it does not hold in all finite convex geometries. This raises a number of representation problems for convex geometries, which may allow us to better understand the properties of Euclidean space related to its dimension.     

A characterization of Möbius transformations by use of hyperbolic regular polygons

In this paper we present a new characterization of Möbius transformations by use of hyperbolic regular polygons.     

A characterization of convex games by means of bargaining sets

The aim of the paper is to characterize the classical convexity notion for cooperative TU games by means of the Mas-Colell and the Davis–Maschler bargaining sets. A new set of payoff vectors is introduced and analyzed: the max-Weber set. This set is defined as the convex hull of the max-marginal worth vectors. The characterizations of convexity are reached by comparing the classical Weber set, the max-Weber set and a selected bargaining set.     

On the approximation of convex functions by Bernstein-type operators

As a consequence of Jensen's inequality, centered operators of probabilistic type (also called Bernstein-type operators) approximate convex functions from above. Starting from this fact, we consider several pairs of classical operators and determine, in each case, which one is better to approximate convex functions. In almost all the discussed examples, the conclusion follows from a simple argument concerning composition of operators. However, when comparing Szász-Mirakyan operators with Bernstein operators over the positive semi-axis, the result is derived from the convex ordering of the involved probability distributions. Analogous results for non-centered operators are also considered.     

Characterizations of strictly convex sets by the uniqueness of support points

Abstract

This short paper characterizes strictly convex sets by the uniqueness of support points (such points are called unique support points or exposed points) under appropriate assumptions. A class of so-called regular sets, for which every extreme point is a unique support point, is introduced. Closed strictly convex sets and their intersections with some other sets are shown to belong to this class. The obtained characterizations are then applied to set-valued maps and to the separation of a convex set and a strictly convex set. Under suitable assumptions, so-called set-valued maps with path property are characterized by strictly convex images of the considered set-valued map.     

Characterizations of counter-monotonicity and upper comonotonicity by (tail) convex order

In this paper, we characterize counter-monotonic and upper comonotonic random vectors by the optimality of the sum of their components in the senses of the convex order and tail convex order respectively. In the first part, we extend the characterization of comonotonicity by  Cheung (2010) and show that the sum of two random variables is minimal with respect to the convex order if and only if they are counter-monotonic. Three simple and illuminating proofs are provided. In the second part, we investigate upper comonotonicity by means of the tail convex order. By establishing some useful properties of this relatively new stochastic order, we prove that an upper comonotonic random vector must give rise to the maximal tail convex sum, thereby completing the gap in  Nam et al. (2011)’s characterization. The relationship between the tail convex order and risk measures along with conditions under which the additivity of risk measures is sufficient for upper comonotonicity is also explored.     

The limiting normality of the test statistic for the two-sample problem induced by a convex sum distance

Critchlow (1992, J. Statist. Plann. Inference, 32, 325–346) proposed a method of a unified construction of a class of rank tests. In this paper, we introduce a convex sum distance and prove the limiting normality of the test statistics for the two-sample problem derived by his method.     

Approximation of convex bodies by multiple objective optimization and an application in reachable sets

In this paper, we focus on approximating convex compact bodies. For a convex body described as the feasible set in objective space of a multiple objective programme, we show that finding it is equivalent to finding the non-dominated set of a multiple objective programme. This equivalence implies that convex bodies can be approximated using multiple objective optimization algorithms. Therefore, we propose a revised outer approximation algorithm for convex multiple objective programming problems to approximate convex bodies. Finally, we apply the algorithm to solve reachable sets of control systems and use numerical examples to show the effectiveness of the algorithm.     

A unified class of k-uniformly convex functions defined by the Dziok–Srivastava linear operator

The main purpose of this paper is to introduce a new class of functions which are analytic in the open unit disk . We obtain various results including characterization, coefficient estimates, and distortion and covering theorems, for functions belonging to the class .     

Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method

Let be a 0-1 quadratic program which consists in minimizing a quadratic function subject to linear equality constraints. In this paper, we present QCR, a general method to reformulate into an equivalent 0-1 program with a convex quadratic objective function. The reformulated problem can then be efficiently solved by a classical branch-and-bound algorithm, based on continuous relaxation. This idea is already present in the literature and used in standard solvers such as CPLEX. Our objective in this work was to find a convex reformulation whose continuous relaxation bound is, moreover, as tight as possible. From this point of view, we show that QCR is optimal in a certain sense. State-of-the-art reformulation methods mainly operate a perturbation of the diagonal terms and are valid for any {0,1} vector. The innovation of QCR comes from the fact that the reformulation also uses the equality constraints and is valid on the feasible solution domain only. Hence, the superiority of QCR holds by construction. However, reformulation by QCR requires the solution of a semidefinite program which can be costly from the running time point of view. We carry out a computational experience on three different combinatorial optimization problems showing that the costly computational time of reformulation by QCR can however result in a drastically more efficient branch-and-bound phase. Moreover, our new approach is competitive with very specific methods applied to particular optimization problems.