HOME

TheInfoList



OR:

A convex polytope is a special case of a polytope, having the additional property that it is also a
convex set In geometry, a subset of a Euclidean space, or more generally an affine space over the reals, is convex if, given any two points in the subset, the subset contains the whole line segment that joins them. Equivalently, a convex set or a convex ...
contained in the n-dimensional Euclidean space \mathbb^n. Most texts. use the term "polytope" for a bounded convex polytope, and the word "polyhedron" for the more general, possibly unbounded object. Others''Mathematical Programming'', by Melvyn W. Jeter (1986)
p. 68
/ref> (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. Convex polytopes play an important role both in various branches of
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
and in applied areas, most notably in
linear programming Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is ...
. In the influential textbooks of Grünbaum and Ziegler 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 n-dimensional object in \mathbb^n.


Examples

*Many examples of bounded convex polytopes can be found in the article "
polyhedron In geometry, a polyhedron (plural polyhedra or polyhedrons; ) is a three-dimensional shape with flat polygonal faces, straight edges and sharp corners or vertices. A convex polyhedron is the convex hull of finitely many points, not all o ...
". *In the 2-dimensional case the full-dimensional examples are a half-plane, a strip between two parallel lines, an
angle In Euclidean geometry, an angle is the figure formed by two rays, called the '' sides'' of the angle, sharing a common endpoint, called the ''vertex'' of the angle. Angles formed by two rays lie in the plane that contains the rays. Angles ...
shape (the intersection of two non-parallel half-planes), a shape defined by a convex polygonal chain with two
ray Ray may refer to: Fish * Ray (fish), any cartilaginous fish of the superorder Batoidea * Ray (fish fin anatomy), a bony or horny spine on a fin Science and mathematics * Ray (geometry), half of a line proceeding from an initial point * Ray (gr ...
s attached to its ends, and a convex polygon. *Special cases of an unbounded convex polytope are a slab between two parallel hyperplanes, a wedge defined by two non-parallel half-spaces, a polyhedral cylinder (infinite prism), and a polyhedral cone (infinite cone) defined by three or more half-spaces passing through a common point.


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 ''Convex Polytopes'' is a graduate-level mathematics textbook about convex polytopes, higher-dimensional generalizations of three-dimensional convex polyhedra. It was written by Branko Grünbaum, with contributions from Victor Klee, Micha Perl ...
'', Grünbaum defines a convex polytope as a
compact Compact as used in politics may refer broadly to a pact or treaty; in more specific cases it may refer to: * Interstate compact * Blood compact, an ancient ritual of the Philippines * Compact government, a type of colonial rule utilized in Britis ...
convex set In geometry, a subset of a Euclidean space, or more generally an affine space over the reals, is convex if, given any two points in the subset, the subset contains the whole line segment that joins them. Equivalently, a convex set or a convex ...
with a finite number of
extreme points In mathematics, an extreme point of a convex set S in a real or complex vector space is a point in S which does not lie in any open line segment joining two points of S. In linear programming problems, an extreme point is also called vertex ...
: : A set K of \mathbb^n is ''convex'' if, for each pair of distinct points a, b in K, the closed segment with endpoints a and b is contained within K. 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). For a compact convex polytope, the minimal V-description is unique and it is given by the set of the vertices of the polytope. A convex polytope is called an
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 c ...
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). 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. A
closed half-space In geometry, a half-space is either of the two parts into which a plane divides the three-dimensional Euclidean space. If the space is two-dimensional, then a half-space is called a half-plane (open or closed). A half-space in a one-dimensional ...
can be written as a linear inequality: Branko Grünbaum, ''
Convex Polytopes ''Convex Polytopes'' is a graduate-level mathematics textbook about convex polytopes, higher-dimensional generalizations of three-dimensional convex polyhedra. It was written by Branko Grünbaum, with contributions from Victor Klee, Micha Perl ...
'', 2nd edition, prepared by Volker Kaibel, Victor Klee, and Günter M. Ziegler, 2003, , , 466pp.
:a_1 x_1 + a_2 x_2 + \cdots + a_n x_n \leq b where n 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: :\begin a_ x_1 &&\; + \;&& a_ x_2 &&\; + \cdots + \;&& a_ x_n &&\; \leq \;&&& b_1 \\ a_ x_1 &&\; + \;&& a_ x_2 &&\; + \cdots + \;&& a_ x_n &&\; \leq \;&&& b_2 \\ \vdots\;\;\; && && \vdots\;\;\; && && \vdots\;\;\; && &&& \;\vdots \\ a_ x_1 &&\; + \;&& a_ x_2 &&\; + \cdots + \;&& a_ x_n &&\; \leq \;&&& b_m \\ \end where m is the number of half-spaces defining the polytope. This can be concisely written as the
matrix Matrix most commonly refers to: * ''The Matrix'' (franchise), an American media franchise ** '' The Matrix'', a 1999 science-fiction action film ** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchi ...
inequality: :Ax \leq b where A is an m\times n matrix, x is an n\times1 column vector whose coordinates are the variables x_1 to x_n, and b is an m\times1 column vector whose coordinates are the right-hand sides b_1 to b_m 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 A and b 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 Ax\leq b lie in a proper affine subspace of \mathbb^n 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. 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''. 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 vector In mathematics, physics, and engineering, a Euclidean vector or simply a vector (sometimes called a geometric vector or spatial vector) is a geometric object that has magnitude (or length) and direction. Vectors can be added to other vectors ...
s of its infinite edges (its "defining rays"). This is called the finite basis theorem.


Properties

Every (bounded) convex polytope is the image of a
simplex In geometry, a simplex (plural: simplexes or simplices) 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 dimension. ...
, 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 Half-space may refer to: * Half-space (geometry), either of the two parts into which a plane divides Euclidean space * Half-space (punctuation), a spacing character half the width of a regular space * (Poincaré) Half-space model, a model of 3-dime ...
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. 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 Ax \leq b, 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''. 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 In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word i ...
. 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 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 Micah (; ) is a given name. Micah is the name of several people in the Hebrew Bible (Old Testament), and means "Who is like God?" The name is sometimes found with theophoric extensions. Suffix theophory in '' Yah'' and in ''Yahweh'' results in M ...
). Kalai (1988) 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.


Topological properties

A convex polytope, like any compact convex subset of R''n'', is homeomorphic to a closed ball.
Glen E. Bredon Glen Eugene Bredon (August 24, 1932 in Fresno, California – May 8, 2000, in North Fork, California) was an American mathematician who worked in the area of topology. Education and career Bredon received a bachelor's degree from Stanford Univ ...
, ''Topology and Geometry'', 1993, , p. 56.
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 In mathematics, a manifold is a topological space that locally resembles Euclidean space near each point. More precisely, an n-dimensional manifold, or ''n-manifold'' for short, is a topological space with the property that each point has a n ...
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 A tessellation or tiling is the covering of a surface, often a plane, using one or more geometric shapes, called ''tiles'', with no overlaps and no gaps. In mathematics, tessellation can be generalized to higher dimensions and a variety of ...
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.


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 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 ...
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 Algorithms that construct convex hulls of various objects have a broad range of applications in mathematics and computer science. In computational geometry, numerous algorithms are proposed for computing the convex hull of a finite set of point ...
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
polygon In geometry, a polygon () is a plane figure that is described by a finite number of straight line segments connected to form a closed '' polygonal chain'' (or ''polygonal circuit''). The bounded plane region, the bounding circuit, or the two ...
s, i.e., by the ordered sequence of its vertices v_1,\dots, v_m. When the input list of vertices (or edges) is unordered, the
time complexity In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...
of the problems becomes O(''m'' log ''m''). A matching
lower bound In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is greater than or equal to every element of . Dually, a lower bound or minorant of is defined to be an elemen ...
is known in the
algebraic decision tree In computational complexity the decision tree model is the model of computation in which an algorithm is considered to be basically a decision tree, i.e., a sequence of ''queries'' or ''tests'' that are done adaptively, so the outcome of the previ ...
model of computation.


Volume computation

The task of computing the
volume Volume is a measure of occupied three-dimensional space. It is often quantified numerically using SI derived units (such as the cubic metre and litre) or by various imperial or US customary units (such as the gallon, quart, cubic inch). ...
of a convex polytope has been studied in the field of
computational geometry Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems ar ...
. The volume can be computed approximately, for instance, using the convex volume approximation technique, when having access to a membership
oracle An oracle is a person or agency considered to provide wise and insightful counsel or prophetic predictions, most notably including precognition of the future, inspired by deities. As such, it is a form of divination. Description The word ...
. As for exact computation, one obstacle is that, when given a representation of the convex polytope as an equation system of
linear inequalities Linearity is the property of a mathematical relationship (''function'') that can be graphically represented as a straight line. Linearity is closely related to '' proportionality''. Examples in physics include rectilinear motion, the linear r ...
, the volume of the polytope may have a
bit-length Bit-length or bit width is the number of binary digits, called bits, necessary to represent an unsigned integer as a binary number. Formally, the bit-length of a natural number n \geq 0 is :\ell(n) = \lceil \log_2(n+1) \rceil where \log_2 is th ...
which is not polynomial in this representation.


See also

* Oriented matroid * Nef polyhedron *
Steinitz's theorem In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the 3-vertex-connected planar gra ...
for convex polyhedra


References


External links

* * * Komei Fukuda
Polyhedral computation FAQ
{{DEFAULTSORT:Convex Polytope Polytopes Polytope