Building convex polytopes

[Erik Demaine and others]

There are several different ways to specify convex polytopes in three dimensions. The obvious explicit representation is a list of the vertex coordinates and connectivity information between the vertices, edges, and facets. But not all this information is necessary. For example, we can reconstruct the explicit representation given only the coordinates of the vertices; this is the well­studied convex hull problem. By projective duality, we can also reconstruct the polytope from the plane equations of its facets and one interior point, or equivalently, from a list of halfspaces whose intersection is the polytope.

These are not the only ways to uniquely specify a polytope, however. Here I'll list several different theorems describing surprisingly small sets of information that are sufficient to specify 3­dimensional convex polytopes. As far as I know, the algorithmic versions of these theorems are still open.

Nets ("unfoldings")

A polyhedral metric on the sphere assigns to each point a neighborhood that is either isometric to an open planar disk, except for a finite number of points whose neighborhoods are isometric to the apex of a cone. If the complete angle around every cone point is at most 2pi, the metric is said to be convex. Equivalently, a polyhedral metric is obtained by gluing together edges of a simple polygon together in equal­length pairs, so that the resulting 2­complex complex is homeomorphic to a sphere; the metric is convex if the sum of the angles incident to each vertex is at most 2pi. This glued simple polygon is called a net.


A net for the cube.

Any convex 3­polytope naturally defines a polyhedral metric; the "distance" between two points is just the length of the shortest path on the polytope's surface. A beautiful and surprising result of Aleksandrov is that the converse is true as well.

Aleksandrov's Theorem: Any convex polyhedral metric can be realized by a unique convex polytope (up to congruence).
For any convex polytope, we can define a net by "unfolding" it into the plane. It is open whether every polytope can be unfolded into a simple net, that is, one that does not overlap itself, by cutting along edges; however, even non­simple nets can be used to define polyhedral metrics. Aleksandrov's theorem states that any net is an unfolding of a unique convex polytope (up to congruence).

Given a net (a simple polygon with edge­matching rules), how quickly can we construct the corresponding polytope? This actually requires solving two separate subproblems. The first is to find the preimages of the polytope edges on the polygon; this is usually called the crease pattern. Note that the crease pattern, and thus the resulting polytope, depends on the geometric shape of the net as well as its combinatorial structure.


Two combinatorially equivalent nets with different crease patterns (after Herbert Edelsbrunner).
Colors indicate the resulting polytope facets.

Given a net, how quickly can we find the corresponding crease pattern? This problem at least seems to have a polynomial­time solution. Boris Aronov and Joe O'Rourke observed that we can obtain a superset of the creases by finding all shortest paths, in the polyhedral metric defined by the net, between every pair of vertices. (Note that there could be several shortest paths between the same two vertices!) This gives us a segment arrangement with (roughly) O(n5) vertices, which can be computed in polynomial time. The O(n) actual creases are a subset of this arrangement, but no algorithm is known to isolate them.


All shortest paths from one vertex and all shortest paths between every pair of vertices on the cube net.

Once we've found (a superset of) the creases, we have the shapes of the faces and the complete adjacency information -- which faces are adjacent along which edges. If two polytopes have the same faces and the same adjacency pattern, they are called stereoisomers. For example, if we start with a regular icosahedron and buckle one five­sided pyramid inward, the result is a stereoisomer of the original icosahedron. A key step in the proof of (the uniqueness part of) Aleksandrov's theorem is the following beautiful result of Cauchy:

Cauchy's Rigidity Theorem: Convex stereoisomers are congruent.
In other words, any set of polygons with adjacency information can be obtained from at most one polytope, and (by the existence part of Aleksandrov's theorem) this polytope exists as long as the resulting complex is homeomorphic to the sphere. How quickly can we construct this polytope? Cauchy's proof is nonconstructive. Although a numerical approximation algorithm seems quite likely, I would be much happier with a purely combinatorial algorithm that runs in polynomial time. This may require a model of computation that allows exact computation (or at least useful representations) of high­degree algebraic numbers.

Here's a related open question. It is quite easy to construct sets of polygons (without adjacency information) that cannot be assembled into polytopes, or that can be assembled into more than one polytope. In particular, except for the infinite families of prisms and antiprisms, only a finite number of polytopes can be constructed using regular polygons. Given a set of convex polygons, how quickly can we decide whether they can be assembled into a convex polytope? Into a unique convex polytope? How quickly can we actually construct a polytope with a given set of facets, if one exists? I conjecture that these problems are NP­hard.

Area­weighted normal vectors

A fairly simple theorem of Minkowski states that if you take the normal vectors of the facets of a convex polytope, where the length of the vector is the area of the corresponding facet, then the resulting collection of vectors sum to zero. In fact, this theorem is true in any dimension (where "area" means the natural (d-1)­dimensional Lebesgue measure). But the more interesting part of Minkowski's theorem is that this process is reversible:
Minkowski's Theorem: Any set of vectors whose sum is zero is the set of area­weighted normals of a unique convex polytope (up to translation).
Given a collection of vectors that sum to zero, how quickly can we construct the corresponding polytope? As with Cauchy's Rigidity Theorem, there are numerical approximation algorithms, but I'm looking for a purely combinatorial algorithm.

Franz Aurenhammer, Friedrich Hoffman, and Boris Aronov proved the following discrete analog of Minkowski's theorem. For any set P of n "red" points and m "blue" points on the sphere, and for any assignment of capacities to the red points such that the sum of the capacities is m, it is possible to weight the red points so that for each red point p, the number of blue points in the weighted Voronoi region of p is equal to the capacity of p. Minkowski's theorem replaces the blue points with a uniform probability distribution. Aurenhammer, Hoffman, and Aronov give a polynomial­time algorithm for the discrete problem. They also describe an iterative numerical approximation algorithm for the continuous problem (for any probability distribution), by reducing it to a convex optimization problem.

1­skeleta ("edge graphs")

Steinitz's Theorem: Any 3­connected planar graph is the 1­skeleton of a (not necessarily unique) convex polytope.
Given a 3­connected planar graph, how quickly can we construct a polytope whose 1­skeleton is that graph? Perhaps the simplest way to construct such a polytope is to use the following theorem of Paul Koebe, independently proved by Bill Thurston using results of E. M. Andreev.
Koebe's Theorem: Any planar graph is the contact graph of a set of circular disks in the plane or circular caps on the sphere. If the graph is a triangulation, the set of disks is unique up to linear fractional transformations (rigid motions and inversions in circles).

Koebe's theorem can be used to prove the following much stronger version of Steinitz's theorem, which gives a unique "canonical" polytope representation of a graph. (The history of this theorem is a bit confused, but overlapping portions of the theorem were independently proved -- but not necessarily published -- by Walter Brägger, Peter Doyle, Oded Schramm, and Bill Thurston.)

Theorem: Any 3­connected planar graph is the 1­skeleton of a polytope with edges tangent to the unit sphere, such that the barycenter of the contact points is the origin. This polytope is unique up to reflections and rotations about the origin, and every combinatorial symmetry of the graph is realized by a symmetry of the polytope. Each edge of the polytope meets the corresponding edge of the polar dual polytope at right angles at the contact point on the sphere.
Given a 3­connected planar graph, how quickly can we construct its "canonical" polytope? This essentially boils down to finding an algorithmic version of Koebe's theorem. How quickly can we construct a set of disks with a given planar contact graph? The proofs of Koebe, Andreev, and Thurston are nonconstructive, as are later proofs by Brägger, Colin de Verdière, Doyle, and Schramm. Bojan Mohar and Warren Smith independently developed numerical approximation algorithms that output B­bit approximations of the positions and radii in time polynomial in n and B. No purely combinatorial algorithm is known, which is perhaps not surprising since the radii could be high­degree algebraic numbers.

Here's another related open question. How hard is it to decide if a collection of sticks (line segments subject to rigid motions) can be joined to form the 1­skeleton of a convex polytope? The corresponding two­dimensional question has an easy answer: A set of sticks can be assembled into a convex polygon if and only if the longest stick is shorter than all the other sticks put together. Like the earlier problem about building polytopes with a given set of facets, I suspect the 3d problem is NP­hard.

Open Problems - Jeff Erickson (jeffe@cs.uiuc.edu) 03 Nov 2000