N-dimensional polyhedron

Last updated January 31, 2024

An n-dimensional polyhedron is a geometric object that generalizes the 3-dimensional polyhedron to an n-dimensional space. It is defined as a set of points in real affine (or Euclidean) space of any dimension n, that has flat sides. It may alternatively be defined as the intersection of finitely many half-spaces. Unlike a 3-dimensional polyhedron, it may be bounded or unbounded. In this terminology, a bounded polyhedron is called a polytope.^[1]^[2]

Analytically, a convex polyhedron is expressed as the solution set for a system of linear inequalities, a_i^Tx ≤ b_i, where a_i are vectors in Rⁿ and b_i are scalars. This definition of polyhedra is particularly important as it provides a geometric perspective for problems in linear programming.^[3]^: 9

Examples

Many traditional polyhedral forms are n-dimensional polyhedra. Other examples include:

A half-space is a polyhedron defined by a single linear inequality, a₁^Tx ≤ b₁.
A hyperplane is a polyhedron defined by two inequalities, a₁^Tx ≤ b₁ and a₁^Tx ≥ b₁ (which is equivalent to -a₁^Tx ≤ -b₁).
A quadrant in the plane. For instance, the region of the cartesian plane consisting of all points above the horizontal axis and to the right of the vertical axis: ${ (x, y) : x \geq 0, y \geq 0$ }. Its sides are the two positive axes, and it is otherwise unbounded.
An octant in Euclidean 3-space, ${ (x, y, z) : x \geq 0, y \geq 0, z \geq 0$ }.
A prism of infinite extent. For instance a doubly infinite square prism in 3-space, consisting of a square in the xy-plane swept along the z-axis: ${ (x, y, z) : 0 \leq x \leq 1, 0 \leq y \leq 1$ }.
Each cell in a Voronoi tessellation is a polyhedron. In the Voronoi tessellation of a set S, the cell A corresponding to a point $c \in S$ is bounded (hence a traditional polyhedron) when c lies in the interior of the convex hull of S, and otherwise (when c lies on the boundary of the convex hull of S) A is unbounded.

Faces and vertices

A subset F of a polyhedron P is called a face of P if there is a halfspace H (defined by some inequality a₁^Tx ≤ b₁) such that H contains P and F is the intersection of H and P.^[3]^: 9

If a face contains a single point {v}, then v is called a vertex of P.
If a face F is nonempty and n-1 dimensional, then F is called a facet of P.

Suppose P is a polyhedron defined by Ax ≤ b, where A has full column rank. Then, v is a vertex of P if and only if v is a basic feasible solution of the linear system Ax ≤ b.^[3]^: 10

Standard representation

The representation of a polyhedron by a set of linear inequalities is not unique. It is common to define a standard representation for each polyhedron P:^[3]^: 9

If P is full-dimensional, then its standard representation is a set of inequalities such that each inequality a_i^Tx ≤ b_i defines exactly one facet of P, and moreover, the inequalities are normalized such that $\|a_{i}\|_{\infty }=1$ for all i.
If P is not full-dimensional, then it is contained in its affine hull, which is defined by a set of linear equations Cx=d. It is possible to choose C such that C = (I, C'), where I is an identity matrix. The standard representation of P contains this set Cx=d and a set of inequalities such that each inequality a_i^Tx ≤ b_i defines exactly one facet of P, the inequalities are normalized such that $\|a_{i}\|_{\infty }=1$ for all i, and each a_i is orthogonal to each row of C. This representation is unique up to the choice of columns of the identity matrix.

Representation by cones and convex hulls

If P is a polytope (a bounded polyhedron), then it can be represented by its set of vertices V, as P is simply the convex hull of V: P = conv(V).

If P is a general (possibly unbounded) polyhedron, then it can be represented as: P = conv(V) + cone(E), where V is (as before) the set of vertices of P, and E is another finite set, and cone denotes the conic hull. The set cone(E) is also called the recession cone of P.^[3]^: 10

Carathéodory's theorem states that, if P is a d-dimensional polytope, then every point in P can be written as a convex combination of at most d+1 affinely-independent vertices of P. The theorem can be generalized: if P is any d-dimensional polyhedron, then every point in P can be written as a convex combination of points v₁,...,v_s, v₁+e₁,...,v₁+e_t with s+t ≤ d+1, such that v₁,...,v_s are elements of minimal nonempty faces of P and e₁,...,e_t are elements of the minimal nonzero faces of the recession cone of P.^[3]^: 10

Complexity of representation

When solving algorithmic problems on polyhedra, it is important to know whether a certain polyhedron can be represented by an encoding with a small number of bits. There are several measures to the representation complexity of a polyhedron P:^[3]^: 163

P has facet complexityat most f, if P can be represented by a system of linear inequalities with rational coefficients, such that the encoding length of each inequality (i.e., the binary encoding length of all rational numbers appearing as coefficients in the inequality) is at most f. Note that f ≥ n+1, since there are n+1 coefficients in each inequality.
P has vertex complexity at most v, if P can be represented as conv(V)+cone(E), where V and E are finite sets, such that each point in V or E has encoding length at most v. Note that v ≥ n, since there are n coefficients in each vector.

These two kinds of complexity are closely related:^[3]^{: Lem.6.2.4}

If P has facet complexity at most f, then P has vertex complexity at most 4 n²f.
If P has vertex complexity at most v, then P has facet complexity at most 3 n²v.

A polyhedron P is called well-described if we know n (the number of dimensions) and f (an upper bound on the facet complexity).

In some cases, we know an upper bound on the facet complexity of a polyhedron P, but we do not know the specific inequalities that attain this upper bound. However, it can be proved that the encoding length in any standard representation of P is at most 35 n²f. ^[3]^{: Lem.6.2.3}

The complexity of representation of P implies upper and lower bounds on the volume of P:^[3]^: 165

If P has vertex complexity at most v, then trivially, all vertices of P are contained in the ball of radius 2^v around the origin. This means that, if P is a polytope, then P itself is circumscribed in that ball.
If P is a full-dimensional polyhedron with facet complexity at most f, then P contains a ball with radius $2^{-7n^{3}f}$ . Moreover, this ball is contained in the ball of radius $2^{5n^{2}f}$ around the origin.

Small representation complexity is useful for "rounding" approximate solutions to exact solutions. Specifically:^[3]^: 166

If P is a polyhedron with facet complexity at most f, and y is a rational vector whose entries have common denominator at most q, and the distance from y to P is at most 2^-2f/q, then y is in fact in P.
If P is a polyhedron with vertex complexity at most v, and P satisfies the inequality a^Tx ≤ b + 2^-v-1, then P also satisfies the inequality a^Tx ≤ b.
If P is a polyhedron with facet complexity at most f, and v is a rational vector with distance from P of at most 2^-6nf, and q and w are integer vectors satisfying $\|qv-w\|<2^{-3f},0<q<2^{4nf}$ , then the point w/q is contained in P. The number q and the vector w can be found in polytime using simultaneous diophantine approximation.
If P is a polyhedron with vertex complexity at most v, and P satisfies the inequality a^Tx ≤ b + 2^-6nv, and q,c,d are integer vectors satisfying $\|qa-c\|+|qb-d|<2^{-3v},0<q<2^{4nv}$ , then P satisfies the inequality c^Tx ≤ d. The numbers q,d and the vector c can be found in polytime using simultaneous diophantine approximation.

Related Research Articles

In geometry, every polyhedron is associated with a second dual structure, 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 can also be constructed as geometric polyhedra. Starting with any given polyhedron, the dual of its dual is the original polyhedron.

<span class="mw-page-title-main">Polyhedron</span> 3D shape with flat 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.

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

Linear programming (LP), also called linear optimization, is a method to achieve the best outcome in a mathematical model whose requirements and objective are represented by linear relationships. Linear programming is a special case of mathematical programming.

In solid geometry, a face is a flat surface that forms part of the boundary of a solid object; a three-dimensional solid bounded exclusively by faces is a polyhedron.

<span class="mw-page-title-main">Schläfli symbol</span> Notation that defines regular polytopes and tessellations

In geometry, the Schläfli symbol is a notation of the form $that defines regular polytopes and tessellations.$

In mathematics, a regular polytope is a polytope whose symmetry group acts transitively on its flags, thus giving it the highest degree of symmetry. In particular, all its elements or $j$ -faces — cells, faces and so on — are also transitive on the symmetries of the polytope, and are themselves regular polytopes of dimension $j \leq n$ .

In mathematics, a duality translates concepts, theorems or mathematical structures into other concepts, theorems or structures in a one-to-one fashion, often by means of an involution operation: if the dual of $A$ is $B$ , then the dual of $B$ is $A$ . Such involutions sometimes have fixed points, so that the dual of $A$ is $A$ itself. For example, Desargues' theorem is self-dual in this sense under the standard duality in projective geometry.

<span class="mw-page-title-main">Convex polytope</span> Convex hull of a finite set of points in a Euclidean space

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 use the term "polytope" for a bounded convex polytope, and the word "polyhedron" for the more general, possibly unbounded object. Others 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.$

In linear algebra, a cone—sometimes called a linear cone for distinguishing it from other sorts of cones—is a subset of a vector space that is closed under positive scalar multiplication; that is, $C$ is a cone if $implies for every positive scalar s . A cone need not be convex, or even look like a cone in Euclidean space.$

In mathematical optimization, the ellipsoid method is an iterative method for minimizing convex functions over convex sets. The ellipsoid method generates a sequence of ellipsoids whose volume uniformly decreases at every step, thus enclosing a minimizer of a convex function.

<span class="mw-page-title-main">Edge (geometry)</span> Line segment joining two adjacent vertices in a polygon or polytope

In geometry, an edge is a particular type of line segment joining two vertices in a polygon, polyhedron, or higher-dimensional polytope. In a polygon, an edge is a line segment on the boundary, and is often called a polygon side. In a polyhedron or more generally a polytope, an edge is a line segment where two faces meet. A segment joining two vertices while passing through the interior or exterior is not an edge but instead is called a diagonal.

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.

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.

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 the mathematical discipline of polyhedral combinatorics, the Gale transform turns the vertices of any convex polytope 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 with the same number of points, but 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.

In convex geometry and the geometry of convex polytopes, the Blaschke sum of two polytopes is a polytope that has a facet parallel to each facet of the two given polytopes, with the same measure. When both polytopes have parallel facets, the measure of the corresponding facet in the Blaschke sum is the sum of the measures from the two given polytopes.

Many problems in mathematical programming can be formulated as problems on convex sets or convex bodies. Six kinds of problems are particularly important: optimization, violation, validity, separation, membership and emptiness. Each of these problems has a strong (exact) variant, and a weak (approximate) variant.

References

↑ Grünbaum, Branko (2003), Convex Polytopes, Graduate Texts in Mathematics, vol. 221 (2nd ed.), New York: Springer-Verlag, p. 26, doi:10.1007/978-1-4613-0019-9, ISBN 978-0-387-00424-2, MR 1976856 .
↑ Bruns, Winfried; Gubeladze, Joseph (2009), "Definition 1.1", Polytopes, Rings, and K-theory, Springer Monographs in Mathematics, Dordrecht: Springer, p. 5, CiteSeerX 10.1.1.693.2630 , doi:10.1007/b105283, ISBN 978-0-387-76355-2, MR 2508056 .
1 2 3 4 5 6 7 8 9 10 11 Grötschel, Martin; Lovász, László; Schrijver, Alexander (1993), Geometric algorithms and combinatorial optimization, Algorithms and Combinatorics, vol. 2 (2nd ed.), Springer-Verlag, Berlin, doi:10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, MR 1261419

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[polytope-bounded-12-1] Grünbaum, Branko (2003), Convex Polytopes, Graduate Texts in Mathematics, vol. 221 (2nd ed.), New York: Springer-Verlag, p. 26, doi:10.1007/978-1-4613-0019-9, ISBN 978-0-387-00424-2, MR 1976856 .

[polytope-bounded-22-2] Bruns, Winfried; Gubeladze, Joseph (2009), "Definition 1.1", Polytopes, Rings, and K-theory, Springer Monographs in Mathematics, Dordrecht: Springer, p. 5, CiteSeerX 10.1.1.693.2630 , doi:10.1007/b105283, ISBN 978-0-387-76355-2, MR 2508056 .

[:02-3] 1 2 3 4 5 6 7 8 9 10 11 Grötschel, Martin; Lovász, László; Schrijver, Alexander (1993), Geometric algorithms and combinatorial optimization, Algorithms and Combinatorics, vol. 2 (2nd ed.), Springer-Verlag, Berlin, doi:10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, MR 1261419

[1]

[2]

[3]