Convex polytope

Last updated
A 3-dimensional convex polytope 3dpoly.svg
A 3-dimensional convex polytope

A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the -dimensional Euclidean space . Most texts [1] [2] use the term "polytope" for a bounded convex polytope, and the word "polyhedron" for the more general, possibly unbounded object. Others [3] (including this article) allow polytopes to be unbounded. The terms "bounded/unbounded convex polytope" will be used below whenever the boundedness is critical to the discussed issue. Yet other texts identify a convex polytope with its boundary.

Contents

Convex polytopes play an important role both in various branches of mathematics and in applied areas, most notably in linear programming.

In the influential textbooks of Grünbaum [1] and Ziegler [2] on the subject, as well as in many other texts in discrete geometry, convex polytopes are often simply called "polytopes". Grünbaum points out that this is solely to avoid the endless repetition of the word "convex", and that the discussion should throughout be understood as applying only to the convex variety (p. 51).

A polytope is called full-dimensional if it is an -dimensional object in .

Examples

Definitions

A convex polytope may be defined in a number of ways, depending on what is more suitable for the problem at hand. Grünbaum's definition is in terms of a convex set of points in space. Other important definitions are: as the intersection of half-spaces (half-space representation) and as the convex hull of a set of points (vertex representation).

Vertex representation (convex hull)

In his book Convex Polytopes , Grünbaum defines a convex polytope as a compact convex set with a finite number of extreme points :

A set of is convex if, for each pair of distinct points , in , the closed segment with endpoints and is contained within .

This is equivalent to defining a bounded convex polytope as the convex hull of a finite set of points, where the finite set must contain the set of extreme points of the polytope. Such a definition is called a vertex representation (V-representation or V-description). [1] For a compact convex polytope, the minimal V-description is unique and it is given by the set of the vertices of the polytope. [1] A convex polytope is called an integral polytope if all of its vertices have integer coordinates.

Intersection of half-spaces

A convex polytope may be defined as an intersection of a finite number of half-spaces. Such definition is called a half-space representation (H-representation or H-description). [1] There exist infinitely many H-descriptions of a convex polytope. However, for a full-dimensional convex polytope, the minimal H-description is in fact unique and is given by the set of the facet-defining halfspaces. [1]

A closed half-space can be written as a linear inequality: [1]

where is the dimension of the space containing the polytope under consideration. Hence, a closed convex polytope may be regarded as the set of solutions to the system of linear inequalities:

where is the number of half-spaces defining the polytope. This can be concisely written as the matrix inequality:

where is an matrix, is an column vector whose coordinates are the variables to , and is an column vector whose coordinates are the right-hand sides to of the scalar inequalities.

An open convex polytope is defined in the same way, with strict inequalities used in the formulas instead of the non-strict ones.

The coefficients of each row of and correspond with the coefficients of the linear inequality defining the respective half-space. Hence, each row in the matrix corresponds with a supporting hyperplane of the polytope, a hyperplane bounding a half-space that contains the polytope. If a supporting hyperplane also intersects the polytope, it is called a bounding hyperplane (since it is a supporting hyperplane, it can only intersect the polytope at the polytope's boundary).

The foregoing definition assumes that the polytope is full-dimensional. In this case, there is a unique minimal set of defining inequalities (up to multiplication by a positive number). Inequalities belonging to this unique minimal system are called essential. The set of points of a polytope which satisfy an essential inequality with equality is called a facet.

If the polytope is not full-dimensional, then the solutions of lie in a proper affine subspace of and the polytope can be studied as an object in this subspace. In this case, there exist linear equations which are satisfied by all points of the polytope. Adding one of these equations to any of the defining inequalities does not change the polytope. Therefore, in general there is no unique minimal set of inequalities defining the polytope.

In general the intersection of arbitrary half-spaces need not be bounded. However if one wishes to have a definition equivalent to that as a convex hull, then bounding must be explicitly required.

Using the different representations

The two representations together provide an efficient way to decide whether a given vector is included in a given convex polytope: to show that it is in the polytope, it is sufficient to present it as a convex combination of the polytope vertices (the V-description is used); to show that it is not in the polytope, it is sufficient to present a single defining inequality that it violates. [4] :256

A subtle point in the representation by vectors is that the number of vectors may be exponential in the dimension, so the proof that a vector is in the polytope might be exponentially long. Fortunately, Carathéodory's theorem guarantees that every vector in the polytope can be represented by at most d+1 defining vectors, where d is the dimension of the space.

Representation of unbounded polytopes

For an unbounded polytope (sometimes called: polyhedron), the H-description is still valid, but the V-description should be extended. Theodore Motzkin (1936) proved that any unbounded polytope can be represented as a sum of a bounded polytope and a convex polyhedral cone. [5] In other words, every vector in an unbounded polytope is a convex sum of its vertices (its "defining points"), plus a conical sum of the Euclidean vectors of its infinite edges (its "defining rays"). This is called the finite basis theorem. [3]

Properties

Every (bounded) convex polytope is the image of a simplex, as every point is a convex combination of the (finitely many) vertices. However, polytopes are not in general isomorphic to simplices. This is in contrast to the case of vector spaces and linear combinations, every finite-dimensional vector space being not only an image of, but in fact isomorphic to, Euclidean space of some dimension (or analog over other fields).

The face lattice

A face of a convex polytope is any intersection of the polytope with a halfspace such that none of the interior points of the polytope lie on the boundary of the halfspace. Equivalently, a face is the set of points giving equality in some valid inequality of the polytope. [4] :258

If a polytope is d-dimensional, its facets are its (d  1)-dimensional faces, its vertices are its 0-dimensional faces, its edges are its 1-dimensional faces, and its ridges are its (d  2)-dimensional faces.

Given a convex polytope P defined by the matrix inequality , if each row in A corresponds with a bounding hyperplane and is linearly independent of the other rows, then each facet of P corresponds with exactly one row of A, and vice versa. Each point on a given facet will satisfy the linear equality of the corresponding row in the matrix. (It may or may not also satisfy equality in other rows). Similarly, each point on a ridge will satisfy equality in two of the rows of A.

The face lattice of a square pyramid, drawn as a Hasse diagram; each face in the lattice is labeled by its vertex set. Pyramid face lattice.svg
The face lattice of a square pyramid, drawn as a Hasse diagram; each face in the lattice is labeled by its vertex set.

In general, an (n  j)-dimensional face satisfies equality in j specific rows of A. These rows form a basis of the face. Geometrically speaking, this means that the face is the set of points on the polytope that lie in the intersection of j of the polytope's bounding hyperplanes.

The faces of a convex polytope thus form an Eulerian lattice called its face lattice, where the partial ordering is by set containment of faces. The definition of a face given above allows both the polytope itself and the empty set to be considered as faces, ensuring that every pair of faces has a join and a meet in the face lattice. The whole polytope is the unique maximum element of the lattice, and the empty set, considered to be a (1)-dimensional face (a null polytope) of every polytope, is the unique minimum element of the lattice.

Two polytopes are called combinatorially isomorphic if their face lattices are isomorphic.

The polytope graph (polytopal graph, graph of the polytope, 1-skeleton) is the set of vertices and edges of the polytope only, ignoring higher-dimensional faces. For instance, a polyhedral graph is the polytope graph of a three-dimensional polytope. By a result of Whitney [6] the face lattice of a three-dimensional polytope is determined by its graph. The same is true for simple polytopes of arbitrary dimension (Blind & Mani-Levitska 1987, proving a conjecture of Micha Perles). [7] Kalai (1988) [8] gives a simple proof based on unique sink orientations. Because these polytopes' face lattices are determined by their graphs, the problem of deciding whether two three-dimensional or simple convex polytopes are combinatorially isomorphic can be formulated equivalently as a special case of the graph isomorphism problem. However, it is also possible to translate these problems in the opposite direction, showing that polytope isomorphism testing is graph-isomorphism complete. [9]

Topological properties

A convex polytope, like any compact convex subset of Rn, is homeomorphic to a closed ball. [10] Let m denote the dimension of the polytope. If the polytope is full-dimensional, then m = n. The convex polytope therefore is an m-dimensional manifold with boundary, its Euler characteristic is 1, and its fundamental group is trivial. The boundary of the convex polytope is homeomorphic to an (m  1)-sphere. The boundary's Euler characteristic is 0 for even m and 2 for odd m. The boundary may also be regarded as a tessellation of (m  1)-dimensional spherical space i.e. as a spherical tiling.

Simplicial decomposition

A convex polytope can be decomposed into a simplicial complex, or union of simplices, satisfying certain properties.

Given a convex r-dimensional polytope P, a subset of its vertices containing (r+1) affinely independent points defines an r-simplex. It is possible to form a collection of subsets such that the union of the corresponding simplices is equal to P, and the intersection of any two simplices is either empty or a lower-dimensional simplex. This simplicial decomposition is the basis of many methods for computing the volume of a convex polytope, since the volume of a simplex is easily given by a formula. [11]

Algorithmic problems for a convex polytope

Construction of representations

Different representations of a convex polytope have different utility, therefore the construction of one representation given another one is an important problem. The problem of the construction of a V-representation is known as the vertex enumeration problem and the problem of the construction of a H-representation is known as the facet enumeration problem. While the vertex set of a bounded convex polytope uniquely defines it, in various applications it is important to know more about the combinatorial structure of the polytope, i.e., about its face lattice. Various convex hull algorithms deal both with the facet enumeration and face lattice construction.

In the planar case, i.e., for a convex polygon, both facet and vertex enumeration problems amount to the ordering vertices (resp. edges) around the convex hull. It is a trivial task when the convex polygon is specified in a traditional way for polygons, i.e., by the ordered sequence of its vertices . When the input list of vertices (or edges) is unordered, the time complexity of the problems becomes O(m log m). [12] A matching lower bound is known in the algebraic decision tree model of computation. [13]

Volume computation

The task of computing the volume of a convex polytope has been studied in the field of computational geometry. The volume can be computed approximately, for instance, using the convex volume approximation technique, when having access to a membership oracle. As for exact computation, one obstacle is that, when given a representation of the convex polytope as an equation system of linear inequalities, the volume of the polytope may have a bit-length which is not polynomial in this representation. [14]

See also

Related Research Articles

Dual polyhedron Polyhedron associated with another by swapping vertices for faces

In geometry, any polyhedron is associated with a second dual figure, where the vertices of one correspond to the faces of the other, and the edges between pairs of vertices of one correspond to the edges between pairs of faces of the other. Such dual figures remain combinatorial or abstract polyhedra, but not all are also geometric polyhedra. Starting with any given polyhedron, the dual of its dual is the original polyhedron.

Polyhedron Three-dimensional shape with flat polygonal faces, straight edges and sharp corners

In geometry, a polyhedron is a three-dimensional shape with flat polygonal faces, straight edges and sharp corners or vertices. The word polyhedron comes from the Classical Greek πολύεδρον, as poly- + -hedron.

In elementary geometry, a polytope is a geometric object with "flat" sides. It is a generalization in any number of dimensions of the three-dimensional polyhedron. Polytopes may exist in any general number of dimensions n as an n-dimensional polytope or n-polytope. Flat sides mean that the sides of a (k+1)-polytope consist of k-polytopes that may have (k−1)-polytopes in common. For example, a two-dimensional polygon is a 2-polytope and a three-dimensional polyhedron is a 3-polytope.

Simplex Multi-dimensional generalization of triangle

In geometry, a simplex is a generalization of the notion of a triangle or tetrahedron to arbitrary dimensions. The simplex is so-named because it represents the simplest possible polytope in any given space.

Hypercube Convex polytope, the n-dimensional analogue of a square and a cube

In geometry, a hypercube is an n-dimensional analogue of a square and a cube. It is a closed, compact, convex figure whose 1-skeleton consists of groups of opposite parallel line segments aligned in each of the space's dimensions, perpendicular to each other and of the same length. A unit hypercube's longest diagonal in n dimensions is equal to .

Hyperplane Geometric object

In geometry, a hyperplane is a subspace whose dimension is one less than that of its ambient space. If a space is 3-dimensional then its hyperplanes are the 2-dimensional planes, while if the space is 2-dimensional, its hyperplanes are the 1-dimensional lines. This notion can be used in any general space in which the concept of the dimension of a subspace is defined.

Cross-polytope Regular polytope dual to the hypercube in any number of dimensions

In geometry, a cross-polytope, hyperoctahedron, orthoplex, or cocube is a regular, convex polytope that exists in n-dimensions. A 2-dimensional cross-polytope is a square, a 3-dimensional cross-polytope is a regular octahedron, and a 4-dimensional cross-polytope is a 16-cell. Its facets are simplexes of the previous dimension, while the cross-polytope's vertex figure is another cross-polytope from the previous dimension.

Arrangement of hyperplanes Partition of linear, affine, or projective space by a finite set of hyperplanes

In geometry and combinatorics, an arrangement of hyperplanes is an arrangement of a finite set A of hyperplanes in a linear, affine, or projective space S. Questions about a hyperplane arrangement A generally concern geometrical, topological, or other properties of the complement, M(A), which is the set that remains when the hyperplanes are removed from the whole space. One may ask how these properties are related to the arrangement and its intersection semilattice. The intersection semilattice of A, written L(A), is the set of all subspaces that are obtained by intersecting some of the hyperplanes; among these subspaces are S itself, all the individual hyperplanes, all intersections of pairs of hyperplanes, etc.. These intersection subspaces of A are also called the flats ofA. The intersection semilattice L(A) is partially ordered by reverse inclusion.

24-cell honeycomb

In four-dimensional Euclidean geometry, the 24-cell honeycomb, or icositetrachoric honeycomb is a regular space-filling tessellation of 4-dimensional Euclidean space by regular 24-cells. It can be represented by Schläfli symbol {3,4,3,3}.

In mathematics, specifically in combinatorial commutative algebra, a convex lattice polytope P is called normal if it has the following property: given any positive integer n, every lattice point of the dilation nP, obtained from P by scaling its vertices by the factor n and taking the convex hull of the resulting points, can be written as the sum of exactly n lattice points in P. This property plays an important role in the theory of toric varieties, where it corresponds to projective normality of the toric variety determined by P. Normal polytopes have popularity in algebraic combinatorics. These polytopes also represent the homogeneous case of the Hilbert bases of finite positive rational cones and the connection to algebraic geometry is that they define projectively normal embeddings of toric varieties.

Permutohedron

In mathematics, the permutohedron of order n is an (n − 1)-dimensional polytope embedded in an n-dimensional space. Its vertex coordinates (labels) are the permutations of the first n natural numbers. The edges identify the shortest possible paths that connect two vertices (permutations). Two permutations connected by an edge differ in only two places, and the numbers on these places are neighbors.

1<sub> 22</sub> polytope

In 6-dimensional geometry, the 122 polytope is a uniform polytope, constructed from the E6 group. It was first published in E. L. Elte's 1912 listing of semiregular polytopes, named as V72 (for its 72 vertices).

4<sub> 21</sub> polytope

In 8-dimensional geometry, the 421 is a semiregular uniform 8-polytope, constructed within the symmetry of the E8 group. It was discovered by Thorold Gosset, published in his 1900 paper. He called it an 8-ic semi-regular figure.

In mathematics, the vertex enumeration problem for a polytope, a polyhedral cell complex, a hyperplane arrangement, or some other object of discrete geometry, is the problem of determination of the object's vertices given some formal representation of the object. A classical example is the problem of enumeration of the vertices of a convex polytope specified by a set of linear inequalities:

Polyhedral combinatorics is a branch of mathematics, within combinatorics and discrete geometry, that studies the problems of counting and describing the faces of convex polyhedra and higher-dimensional convex polytopes.

Integral polytope

In geometry and polyhedral combinatorics, an integral polytope is a convex polytope whose vertices all have integer Cartesian coordinates. That is, it is a polytope that equals the convex hull of its integer points. Integral polytopes are also called lattice polytopes or Z-polytopes. The special cases of two- and three-dimensional integral polytopes may be called polygons or polyhedra instead of polytopes, respectively.

Hypersimplex

In polyhedral combinatorics, the hypersimplex is a convex polytope that generalizes the simplex. It is determined by two integers and , and is defined as the convex hull of the -dimensional vectors whose coefficients consist of ones and zeros. Equivalently, can be obtained by slicing the -dimensional unit hypercube with the hyperplane of equation and, for this reason, it is a -dimensional polytope when .

In mathematics, the order polytope of a finite partially ordered set is a convex polytope defined from the set. The points of the order polytope are the monotonic functions from the given set to the unit interval, its vertices correspond to the upper sets of the partial order, and its dimension is the number of elements in the partial order. The order polytope is a distributive polytope, meaning that coordinatewise minima and maxima of pairs of its points remain within the polytope.

In polyhedral combinatorics, the Gale transform turns the vertices of any convex polytopes into a set of vectors or points in a space of a different dimension, the Gale diagram of the polytope. It can be used to describe high-dimensional polytopes with few vertices, by transforming them into sets of points in a space of a much lower dimension. The process can also be reversed, to construct polytopes with desired properties from their Gale diagrams. The Gale transform and Gale diagram are named after David Gale, who introduced these methods in a 1956 paper on neighborly polytopes.

References

  1. 1 2 3 4 5 6 7 Branko Grünbaum, Convex Polytopes , 2nd edition, prepared by Volker Kaibel, Victor Klee, and Günter M. Ziegler, 2003, ISBN   0-387-40409-0, ISBN   978-0-387-40409-7, 466pp.
  2. 1 2 Ziegler, Günter M. (1995), Lectures on Polytopes, Graduate Texts in Mathematics, 152, Berlin, New York: Springer-Verlag .
  3. 1 2 Mathematical Programming, by Melvyn W. Jeter (1986) ISBN   0-8247-7478-7, p. 68
  4. 1 2 Lovász, László; Plummer, M. D. (1986), Matching Theory, Annals of Discrete Mathematics, 29, North-Holland, ISBN   0-444-87916-1, MR   0859549
  5. Motzkin, Theodore (1936). Beitrage zur Theorie der linearen Ungleichungen (Ph.D. dissertation). Jerusalem.
  6. Whitney, Hassler (1932). "Congruent graphs and the connectivity of graphs". Amer. J. Math. 54 (1): 150–168. doi:10.2307/2371086. hdl: 10338.dmlcz/101067 . JSTOR   2371086.
  7. Blind, Roswitha; Mani-Levitska, Peter (1987), "Puzzles and polytope isomorphisms", Aequationes Mathematicae , 34 (2–3): 287–297, doi:10.1007/BF01830678, MR   0921106 .
  8. Kalai, Gil (1988), "A simple way to tell a simple polytope from its graph", Journal of Combinatorial Theory , Ser. A, 49 (2): 381–383, doi: 10.1016/0097-3165(88)90064-7 , MR   0964396 .
  9. Kaibel, Volker; Schwartz, Alexander (2003). "On the Complexity of Polytope Isomorphism Problems". Graphs and Combinatorics . 19 (2): 215–230. arXiv: math/0106093 . doi:10.1007/s00373-002-0503-y. Archived from the original on 2015-07-21.
  10. Glen E. Bredon, Topology and Geometry, 1993, ISBN   0-387-97926-3, p. 56.
  11. Büeler, B.; Enge, A.; Fukuda, K. (2000). "Exact Volume Computation for Polytopes: A Practical Study". Polytopes — Combinatorics and Computation. p. 131. doi:10.1007/978-3-0348-8438-9_6. ISBN   978-3-7643-6351-2.
  12. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "33.3 Finding the convex hull". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 947–957. ISBN   0-262-03293-7.
  13. Yao, Andrew Chi Chih (1981), "A lower bound to finding convex hulls", Journal of the ACM , 28 (4): 780–787, doi:10.1145/322276.322289, MR   0677089 ; Ben-Or, Michael (1983), "Lower Bounds for Algebraic Computation Trees", Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing (STOC '83), pp. 80–86, doi:10.1145/800061.808735 .
  14. Lawrence, Jim (1991). "Polytope volume computation". Mathematics of Computation. 57 (195): 259–271. doi: 10.1090/S0025-5718-1991-1079024-2 . ISSN   0025-5718.