Automorphisms and Distinguishing Numbers of Geometric Cliques

A geometric automorphism is an automorphism of a geometric graph that preserves crossings and noncrossings of edges. We prove two theorems constraining the action of a geometric automorphism on the boundary of the convex hull of a geometric clique. First, any geometric automorphism that fixes the boundary of the convex hull fixes the entire clique. Second, if the boundary of the convex hull contains at least four vertices, then it is invariant under every geometric automorphism. We use these results, and the theory of determining sets, to prove that every geometric n-clique in which n≥7 and the boundary of the convex hull contains at least four vertices is 2-distinguishable.     

On Finite Linear Systems Containing Strict Inequalities

This paper deals with linear systems containing finitely many weak and/or strict inequalities, whose solution sets are referred to as evenly convex polyhedral sets. The classical Motzkin theorem states that every (closed and convex) polyhedron is the Minkowski sum of a convex hull of finitely many points and a finitely generated cone. In this sense, similar representations for evenly convex polyhedra have been recently given by using the standard version for classical polyhedra. In this work, we provide a new dual tool that completely characterizes finite linear systems containing strict inequalities and it constitutes the key for obtaining a generalization of Motzkin theorem for evenly convex polyhedra.     

Calculus of convex polyhedra and polyhedral convex functions by utilizing a multiple objective linear programming solver

ABSTRACT

The article deals with operations defined on convex polyhedra or polyhedral convex functions. Given two convex polyhedra, operations like Minkowski sum, intersection and closed convex hull of the union are considered. Basic operations for one convex polyhedron are, for example, the polar, the conical hull and the image under affine transformation. The concept of a P-representation of a convex polyhedron is introduced. It is shown that many polyhedral calculus operations can be expressed explicitly in terms of P-representations. We point out that all the relevant computational effort for polyhedral calculus consists in computing projections of convex polyhedra. In order to compute projections we use a recent result saying that multiple objective linear programming (MOLP) is equivalent to the polyhedral projection problem. Based on the MOLP solver bensolve a polyhedral calculus toolbox for Matlab and GNU Octave is developed. Some numerical experiments are discussed.     

A simple algorithm for building the 3-D convex hull

A new algorithm is given for finding the convex hull of a finite set of distinct points in three-dimensional space. The algorithm finds the faces of the hull one by one, thus gradually building the polyhedron that constitutes the hull. The algorithm is described as developed through stepwise refinement.     

The Fermat problem in Minkowski spaces

A weakly neighborly polyhedral map (w.n.p. map) is a 2-dimensional cell-complex which decomposes a closed 2-manifold without a boundary, such that for every two vertices there is a 2-cell containing them. We prove that there are just five distinct w.n.p. maps on the torus, and that only three of them are geometrically realizable as polyhedra with convex faces.     

A multidimensional generalization of Lagrange’s theorem on continued fractions

A multidimensional geometric analog of Lagrange’s theorem on continued fractions is proposed. The multidimensional generalization of the geometric interpretation of a continued fraction uses the notion of a Klein polyhedron, that is, the convex hull of the set of nonzero points in the lattice ? ⁿ contained inside some n-dimensional simplicial cone with vertex at the origin. A criterion for the semiperiodicity of the boundary of a Klein polyhedron is obtained, and a statement about the nonempty intersection of the boundaries of the Klein polyhedra corresponding to a given simplicial cone and to a certain modification of this cone is proved.     

Interior Klein polyhedra

The convex hull of all integer points of a noncompact polyhedron is closed and is a generalized polyhedron only under certain conditions. It is proved that if only the integer points in the interior of the polyhedron are taken, then most of the conditions can be dropped. Moreover, the object thus obtained has properties resembling those of a Klein polyhedron, and it is a Klein polyhedron in the case of an irrational simplicial cone.     

Infinite Faces of a Perfect Voronoi Polyhedron

Infinite faces of perfect Voronoi polyhedra are studied. The result substantially varies depending on whether the perfect Voronoi polyhedron is considered as the closed or nonclosed convex hull of the set of Voronoi points (see Theorem 1 in Sec. 5 and Theorem 2 in Sec. 7).     

A Complexity Bound on Faces of the Hull Complex

Given a monomial k[x₁,. . . ,x_n]-module M in the Laurent polynomial ring k[x₁^±1, . . . , x_n^±1], the hull complex is defined to be the set of bounded faces of the convex hull of the points {t^a| x^a M} for sufficiently large t. Bayer and Sturmfels conjectured that the faces of this polyhedron are of bounded complexity in the sense that every such face is affinely isomorphic to a subpolytope of the (n – 1)-dimensional permutohedron, which in particular would imply that these faces have at most n! vertices. In this paper we prove that the latter statement is true, and give a counterexample to the stronger conjecture.     

A geometric realization without self-intersections does exist for Dyck's regular map

Even in our decade there is still an extensive search for analogues of the Platonic solids. In a recent paper Schulte and Wills [13] discussed properties of Dyck's regular map of genus 3 and gave polyhedral realizations for it allowing self-intersections. This paper disproves their conjecture in showing that there is a geometric polyhedral realization (without self-intersections) of Dyck's regular map {3, 8}₆ already in Euclidean 3-space. We describe the shape of this new regular polyhedron.     

Decompositions and boundary coverings of non-convex fat polyhedra

We show that any locally-fat (or (α,β)-covered) polyhedron with convex fat faces can be decomposed into O(n) tetrahedra, where n is the number of vertices of the polyhedron. We also show that the restriction that the faces are fat is necessary: there are locally-fat polyhedra with non-fat faces that require Ω(n²) pieces in any convex decomposition. Furthermore, we show that if we want the tetrahedra in the decomposition to be fat themselves, then their number cannot be bounded as a function of n in the worst case. Finally, we obtain several results on the problem where we want to only cover the boundary of the polyhedron, and not its entire interior.     

Some properties of convex hulls of integer points contained in general convex sets

In this paper, we study properties of general closed convex sets that determine the closedness and polyhedrality of the convex hull of integer points contained in it. We first present necessary and sufficient conditions for the convex hull of integer points contained in a general convex set to be closed. This leads to useful results for special classes of convex sets such as pointed cones, strictly convex sets, and sets containing integer points in their interior. We then present a sufficient condition for the convex hull of integer points in general convex sets to be a polyhedron. This result generalizes the well-known result due to Meyer (Math Program 7:223–225, 1974). Under a simple technical assumption, we show that these sufficient conditions are also necessary for the convex hull of integer points contained in general convex sets to be a polyhedron.     

A Polyhedral Model in Euclidean 3-Space of the Six-Pentagon Map of the Projective Plane

In a private communication, Branko Grünbaum asked: “I wonder whether you know anything about the possibility of realizing as a polyhedron in Euclidean 3-space the family of six pentagons, that is a model of the projective plane arising by identifying antipodal points of the regular dodecahedron. Naturally, any realization must have some self-intersections—but is there any realization that is not completely contained in a plane?”We show that it is possible to realize this polyhedron; in our realization five of the six faces are simple polygons. In this model there are sets of three faces, which form a realization of the Möbius strip without self-intersections. There are four variants of the model. We conjecture that in any model of this polyhedron there must be at least one self-intersecting face.     

Complexity of the Delaunay Triangulation of Points on Polyhedral Surfaces

It is well known that the complexity of the Delaunay triangulation of $n$ points in $\RR ^d$, i.e., the number of its simplices, can be $\Omega (n^{\lceil {d}/{2}\rceil })$. In particular, in $\RR ^3$, the number of tetrahedra can be quadratic. Put another way, if the points are uniformly distributed in a cube or a ball, the expected complexity of the Delaunay triangulation is only linear. The case of points distributed on a surface is of great practical importance in reverse engineering since most surface reconstruction algorithms first construct the Delaunay triangulation of a set of points measured on a surface. In this paper we bound the complexity of the Delaunay triangulation of points distributed on the boundary of a given polyhedron. Under a mild uniform sampling condition, we provide deterministic asymptotic bounds on the complexity of the three-dimensional Delaunay triangulation of the points when the sampling density increases. More precisely, we show that the complexity is $O(n^{1.8})$ for general polyhedral surfaces and $O(n\sqrt{n})$ for convex polyhedral surfaces. Our proof uses a geometric result of independent interest that states that the medial axis of a surface is well approximated by a subset of the Voronoi vertices of the sample points.     

Hamiltonicity and combinatorial polyhedra

We say that a polyhedron with 0–1 valued vertices is combinatorial if the midpoint of the line joining any pair of nonadjacent vertices is the midpoint of the line joining another pair of vertices. We show that the class of combinatorial polyhedra includes such well-known classes of polyhedra as matching polyhedra, matroid basis polyhedra, node packing or stable set polyhedra and permutation polyhedra. We show the graph of a combinatorial polyhedron is always either a hypercube (i.e., isomorphic to the convex hull of a k-dimension unit cube) or else is hamilton connected (every pair of nodes is the set of terminal nodes of a hamilton path). This implies several earlier results concerning special cases of combinatorial polyhedra.     

Generalized intersection cuts and a new cut generating paradigm

Intersection cuts are generated from a polyhedral cone and a convex set S whose interior contains no feasible integer point. We generalize these cuts by replacing the cone with a more general polyhedron C. The resulting generalized intersection cuts dominate the original ones. This leads to a new cutting plane paradigm under which one generates and stores the intersection points of the extreme rays of C with the boundary of S rather than the cuts themselves. These intersection points can then be used to generate in a non-recursive fashion cuts that would require several recursive applications of some standard cut generating routine. A procedure is also given for strengthening the coefficients of the integer-constrained variables of a generalized intersection cut. The new cutting plane paradigm yields a new characterization of the closure of intersection cuts and their strengthened variants. This characterization is minimal in the sense that every one of the inequalities it uses defines a facet of the closure.     

Rigidity of certain polyhedra in $ {\bold R}^3 $

We extend the Cauchy theorem stating rigidity of convex polyhedra in . We do not require that the polyhedron be convex nor embedded, only that the realization of the polyhedron in be linear and isometric on each face. We also extend the topology of the surfaces to include the projective plane in addition to the sphere. Our approach is to choose a convenient normal to each face in such a way that as we go around the star of a vertex the chosen normals are the vertices of a convex polygon on the unit sphere. When we can make such a choice at each vertex we obtain rigidity. For example, we can prove that the heptahedron is rigid. Received: March 3, 1999; revised: December 7, 1999.     

The set of all nondominated solutions in linear cases and a multicriteria simplex method

In this note we are interested in the properties of, and methods for locating the set of all nondominated solutions of multiple linear criteria defined over a polyhedron. We first show that the set of all dominated solutions is convex and that the set of all nondominated solutions is a subset of the convex hull of the nondominated extreme points. When the domination cone is polyhedral, we derive a necessary and sufficient condition for a point to be nondominated. The condition is stronger than that of Ref. [1] and enables us to give a simple proof that the set of all nondominated extreme points indeed is connected. In order to locate the entire set of all nondominated extreme points, we derive a generalized version of simplex method—multicriteria simplex method. In addition to some useful results, a necessary and sufficient condition for an extreme point to be nondominated is derived. Examples and computer experience are also given. Finally, we focus on how to generate the entire set of all nondominated solutions through the set of all nondominated extreme points. A decomposition theorem and some necessary and sufficient conditions for a face to be nondominated are derived. We then describe a systematic way to identify the entire set of all nondominated solutions. Through examples, we show that in fact our procedure is quite efficient.     

Convex Hulls of Integral Points

The convex hull of all integral points contained in a compact polyhedron C is obviously a compact polyhedron. If C is not compact, then the convex hull K of its integral points need not be a closed set. However, under some natural assumptions, K is a closed set and a generalized polyhedron. Bibliography: 11 titles.     

On mixed-integer sets with two integer variables

We show that every facet-defining inequality of the convex hull of a mixed-integer polyhedral set with two integer variables is a crooked cross cut (which we defined in 2010). We extend this result to show that crooked cross cuts give the convex hull of mixed-integer sets with more integer variables if the coefficients of the integer variables form a matrix of rank 2. We also present an alternative characterization of the crooked cross cut closure of mixed-integer sets similar to the one on the equivalence of different definitions of split cuts presented in Cook et al. (1990) [4]. This characterization implies that crooked cross cuts dominate the 2-branch split cuts defined by Li and Richard (2008) [8]. Finally, we extend our results to mixed-integer sets that are defined as the set of points (with some components being integral) inside a closed, bounded and convex set.