# Convex polytope

Jump to navigation Jump to search

Broadly speaking, convex polytopes are sets of points in Euclidean space that define a volume without curved elements, dimples, or self-intersections. Any line segment whose endpoints are contained in the set, should be completely contained within the set. Basic examples include the triangle, the square, or the cube. Counterexamples include the sphere, the star, or toroidal polyhedra.

More technically, convex polytopes are a subclass of convex sets. They can defined either through having finitely many vertices, or finitely many facets – a foundational result implies these definitions are equivalent.

Convex polytopes are generally much more well-studied than their abstract counterparts as they have many important applications in science and engineering, particularly convex optimization. Many sources simply use the word "polytope" to mean "convex polytope".

## Relation to other polytope notions

The general notion of polytopes that is dealt with in this wiki is quite broad. It includes things like star polytopes or skew polytopes. A natural way to deal with all of these cases is to consider them as realizations of abstract polytopes. A major drawback to this approach is that it does not give a natural definition for interior or volume of a polytope.

Convex polytopes, through their nature as point sets, have all of these notions defined by default. The interior of a convex polytope is just the topological interior, and its volume is just its Lebesgue measure.

Likewise, it is often possible to give descriptions of convex polytopes that are much simpler than their combinatorial counterparts. For instance, the prism product of two convex polytopes is just their Cartesian product.

## Definition

Recall that a convex set is one where any line segment between points in the set, stays within the set. The convex hull of a set of points is the smallest convex set containing all of these points.

There is general agreement on what a convex polytope is, but there are multiple definitions that arrive at the same set of objects. We first introduce the two definitions provided by Ziegler in Lectures on Polytopes,[1] as they are the simplest to understand:

1. A V-polytope is defined as the convex hull of a finite set. The 'V' in the name reflects that the vertices of the convex hull will be a subset of the original set.
2. An H-polytope is the intersection of finitely many closed half-spaces that is bounded.[note 1] The 'H' in the name reflects that the hyperplanes bounding the facets of the intersection will be a subset of the original set.

A foundational result is that these two definitions are in fact equivalent – they describe the exact same set of objects. While seemingly clear from visual inspection, this is quite tricky to prove; the first proof is attributed to Weyl and Minkowski.[2]

The dimension of a convex polytope is the dimension of its affine hull, i.e. the dimension of the smallest affine subspace of Euclidean space that entirely contains that polytope. If a polytope is defined in, say, 3-dimensional Euclidean space, it may only be 2-dimensional, such as the convex hull of three points in 3-space. Such polytopes are not considered degenerate, but instead simply lower-dimensional.

Grünbaum defines a convex polytope as a compact (closed and bounded) convex set with a finite number of extreme points. This is provably equivalent to the V-polytope definition. Grünbaum does not use the terms "V-polytope" or "H-polytope", instead using the terms "V-representation" and "H-representation", referring to finite sets of points or half-spaces that produce a convex polytope. While every polytope has at least one V-representation and at least one H-representation, actually converting between a V-representation and an H-representation in practice is a nontrivial problem, and a central one in the study of computational geometry.

## References

1. Ziegler, Lectures on Polytopes
2. Gallier, Jean. Polyhedra and Polytopes

## Notes

1. Ziegler uses the term "H-polyhedron" to refer to any intersection of finitely many closed half-spaces, which may be unbounded. This term has no relation to the conventional meaning of polyhedron. For consistency and clarity, this terminology is not used by the wiki.