Minkowski problem for polytopes

Last updated

In the geometry of convex polytopes, the Minkowski problem for polytopes concerns the specification of the shape of a polytope by the directions and measures of its facets. [1] The theorem that every polytope is uniquely determined up to translation by this information was proven by Hermann Minkowski; it has been called "Minkowski's theorem", although the same name has also been given to several unrelated results of Minkowski. [2] The Minkowski problem for polytopes should also be distinguished from the Minkowski problem, on specifying convex shapes by their curvature.

Contents

Specification and necessary conditions

For any -dimensional polytope, one can specify its collection of facet directions and measures by a finite set of -dimensional nonzero vectors, one per facet, pointing perpendicularly outward from the facet, with length equal to the -dimensional measure of its facet. [3] To be a valid specification of a bounded polytope, these vectors must span the full -dimensional space, and no two can be parallel with the same sign. Additionally, their sum must be zero; this requirement corresponds to the observation that, when the polytope is projected perpendicularly onto any hyperplane, the projected measure of its top facets and its bottom facets must be equal, because the top facets project to the same set as the bottom facets. [1]

Minkowski's uniqueness theorem

It is a theorem of Hermann Minkowski that these necessary conditions are sufficient: every finite set of vectors that spans the whole space, has no two parallel with the same sign, and sums to zero describes the facet directions and measures of a polytope. More, the shape of this polytope is uniquely determined by this information: every two polytopes that give rise to the same set of vectors are translations of each other.

Blaschke sums

The sets of vectors representing two polytopes can be added by taking the union of the two sets and, when the two sets contain parallel vectors with the same sign, replacing them by their sum. The resulting operation on polytope shapes is called the Blaschke sum. It can be used to decompose arbitrary polytopes into simplices, and centrally symmetric polytopes into parallelotopes. [2]

Generalizations

With certain additional information (including separating the facet direction and size into a unit vector and a real number, which may be negative, providing an additional bit of information per facet) it is possible to generalize these existence and uniqueness results to certain classes of non-convex polyhedra. [4]

It is also possible to specify three-dimensional polyhedra uniquely by the direction and perimeter of their facets. Minkowski's theorem and the uniqueness of this specification by direction and perimeter have a common generalization: whenever two three-dimensional convex polyhedra have the property that their facets have the same directions and no facet of one polyhedron can be translated into a proper subset of the facet with the same direction of the other polyhedron, the two polyhedra must be translates of each other. However, this version of the theorem does not generalize to higher dimensions. [4] [5]

See also

Related Research Articles

<span class="mw-page-title-main">Dual polyhedron</span> Polyhedron associated with another by swapping vertices for faces

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.

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">Minkowski addition</span> Sums vector sets A and B by adding each vector in A to each vector in B

In geometry, the Minkowski sum of two sets of position vectors A and B in Euclidean space is formed by adding each vector in A to each vector in B:

<span class="mw-page-title-main">Regular polytope</span> Polytope with highest degree of symmetry

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 jn.

In geometry, a zonohedron is a convex polyhedron that is centrally symmetric, every face of which is a polygon that is centrally symmetric. Any zonohedron may equivalently be described as the Minkowski sum of a set of line segments in three-dimensional space, or as a three-dimensional projection of a hypercube. Zonohedra were originally defined and studied by E. S. Fedorove, a Russian crystallographer. More generally, in any dimension, the Minkowski sum of line segments forms a polytope known as a zonotope.

<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.

<span class="mw-page-title-main">Dihedron</span> Polyhedron with 2 faces

A dihedron is a type of polyhedron, made of two polygon faces which share the same set of n edges. In three-dimensional Euclidean space, it is degenerate if its faces are flat, while in three-dimensional spherical space, a dihedron with flat faces can be thought of as a lens, an example of which is the fundamental domain of a lens space L(p,q). Dihedra have also been called bihedra, flat polyhedra, or doubly covered polygons.

Cauchy's theorem is a theorem in geometry, named after Augustin Cauchy. It states that convex polytopes in three dimensions with congruent corresponding faces must be congruent to each other. That is, any polyhedral net formed by unfolding the faces of the polyhedron onto a flat surface, together with gluing instructions describing which faces should be connected to each other, uniquely determines the shape of the original polyhedron. For instance, if six squares are connected in the pattern of a cube, then they must form a cube: there is no convex polyhedron with six square faces connected in the same way that does not have the same shape.

<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.

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 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 graphs. That is, every convex polyhedron forms a 3-connected planar graph, and every 3-connected planar graph can be represented as the graph of a convex polyhedron. For this reason, the 3-connected planar graphs are also known as polyhedral graphs.

<span class="mw-page-title-main">Parallelohedron</span> Polyhedron that tiles space by translation

In geometry, a parallelohedron is a polyhedron that can be translated without rotations in 3-dimensional Euclidean space to fill space with a honeycomb in which all copies of the polyhedron meet face-to-face. There are five types of parallelohedron, first identified by Evgraf Fedorov in 1885 in his studies of crystallographic systems: the cube, hexagonal prism, rhombic dodecahedron, elongated dodecahedron, and truncated octahedron.

The Alexandrov uniqueness theorem is a rigidity theorem in mathematics, describing three-dimensional convex polyhedra in terms of the distances between points on their surfaces. It implies that convex polyhedra with distinct shapes from each other also have distinct metric spaces of surface distances, and it characterizes the metric spaces that come from the surface distances on polyhedra. It is named after Soviet mathematician Aleksandr Danilovich Aleksandrov, who published it in the 1940s.

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.

Convex Polyhedra is a book on the mathematics of convex polyhedra, written by Soviet mathematician Aleksandr Danilovich Aleksandrov, and originally published in Russian in 1950, under the title Выпуклые многогранники. It was translated into German by Wilhelm Süss as Konvexe Polyeder in 1958. An updated edition, translated into English by Nurlan S. Dairbekov, Semën Samsonovich Kutateladze and Alexei B. Sossinsky, with added material by Victor Zalgaller, L. A. Shor, and Yu. A. Volkov, was published as Convex Polyhedra by Springer-Verlag in 2005.

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 Perles, and G. C. Shephard, and published in 1967 by John Wiley & Sons. It went out of print in 1970. A second edition, prepared with the assistance of Volker Kaibel, Victor Klee, and Günter M. Ziegler, was published by Springer-Verlag in 2003, as volume 221 of their book series Graduate Texts in Mathematics.

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.

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 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.

References

  1. 1 2 Klain, Daniel A. (2004), "The Minkowski problem for polytopes", Advances in Mathematics , 185 (2): 270–288, doi: 10.1016/j.aim.2003.07.001 , MR   2060470
  2. 1 2 Grünbaum, Branko (2003), "15.3 Blaschke Addition", Convex Polytopes, Graduate Texts in Mathematics, vol. 221 (2nd ed.), New York: Springer-Verlag, pp. 331–337, doi:10.1007/978-1-4613-0019-9, ISBN   0-387-00424-6, MR   1976856
  3. This description of how to specify the directions and measures follows Grünbaum (2003); Klain (2004) and Alexandrov (2004) uses slightly different information.
  4. 1 2 Alexandrov, Victor (2004), "Minkowski-type and Alexandrov-type theorems for polyhedral herissons", Geometriae Dedicata , 107: 169–186, arXiv: math/0211286 , doi: 10.1007/s10711-004-4090-3 , MR   2110761
  5. Alexandrov, A. D. (2005), Convex Polyhedra, Springer Monographs in Mathematics, Berlin: Springer-Verlag, ISBN   3-540-23158-7, MR   2127379 ; see in particular Chapter 6, Conditions for Congruence of Polyhedra with Parallel Faces, pp. 271–310, and Chapter 7, Existence Theorems for Polyhedra with Prescribed Face Directions, pp. 311–348