Convex polytope

From Polytope Wiki
Jump to navigation Jump to search
A convex polyhedron created from the intersection of various random half-spaces

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[edit | edit source]

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.

Convex sets[edit | edit source]

Let be a set of points in Euclidean space . A convex combination of these points is an affine combination with nonnegative coefficients. In other words, it is a point

where and . For instance, the set of convex combinations of two points is the line segment that joins them, and the set of convex combinations of three affinely independent points is a triangle. In general, the set of convex combinations of a set of n  + 1 affinely independent points is an n -simplex.

A subset of Euclidean space is called convex when it is closed under convex combinations of two points, hence of any amount of points. Examples of convex sets include balls, simplices, and hypercubes. More basic examples are the empty set , which can be called the nullitope, and the entire set .

In general, the union of two convex sets need not be convex. However, the family of convex sets is closed under arbitrary intersection. As a corollary, it's possible to talk about the smallest convex set which contains a given set as a subset. This is the convex hull of , often denoted by . Equivalently, the convex hull of may be defined as the set of all convex combinations of points in .

Definition[edit | edit source]

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][2] 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.

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[edit | edit source]

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

Notes[edit | edit source]

  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.