Inflating 2D Triangulations to 3D Convex Polyhedra Ben Marlin 
  Welcome | Guibas' Conjecture | Realizability | Algorithms | Applet | Counter Example | Sources

Guibas' Conjecture

Guibas' Conjecture:

Let a convex polygon P be given in the xy-plane, along with two triangulations of it: T1 and T2. Assume further that T1 and T2 have no common edges. Then it is always possible to perturb the vertices of P vertically out of the xy-plane (i.e., by displacement parallel to the z-axis) so that the polygon P becomes a spatial polygon P' such that the convex hull of P' is a convex polyhedron consisting of two triangulated cups glued along P'.


The intuition behind this conjecture arises from the fact if we start with a convex polygon P and assign each vertex some vertical variation, we obtain a spatial polygon P'. If we consider the three dimensional convex hull of the spatial polygon P' we obtain a polyhedron P* . Note that all the vertices of P are vertices of P* , and each face of P* can be triangulated by adding edges between the vertices of P* .

When we then project the polyhedron back onto the horizontal plane, we obtain two distinct triangulations T1 and T2 of P where the diagonals are formed by the edges of the triangulated polyhedron P* not contained in the spatial polygon P'. See Theorem 1 for more information on why this is so.

In forming this conjecture Prof. Guibas assumes that perhaps a sufficient condition on T1 and T2 is that they be distinct. It is quite easy to see that this intuition is validated for some simple configurations such as the quadralateral ABCD shown here:

P with T1

P with T2


McGill University School of Computer Science
Ben Marlin - 2001