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



As seen in the Guibas' Conjecture section, the tetrahedron pictured here was produced by raising two of the polygon's vertices (B and D) out of the plane. We say that the two triangulations T1 and T2 of the quadrilateral ABCD are realizable since we are able to create a convex polyhedron (the tetrahedron) whose convex hull projects back onto T1 and T2. Formally, we have the following:

Definition: A polygon along with two triangulations T1 and T2 is said to be realizable if each vertex in P can be assigned a height such that the edges of the top of the convex hull of the spatial polygon P' project onto T1, and the edges of the bottom of the convex hull of the spatial polygon P' project onto T2.

In the case of the above tetrahedron, the spatial polygon is defined by the edges AB, BC, CD, and DA shown in black. These edges are the only edges common to both the top and the bottom of the convex hull of the spatial polygon. The remaining edge of the bottom is AC shown in blue, while the remaining edge of the top is BD shown in red.

Realizability of Convex Quadrilaterals:

It should be intuitively obvious that the diagonal triangulations of any convex quadrilateral are realizable. Since the number of diagonals in a diagonalization of a convex polygon of n sides is always n-3, the diagonalization of a convex quadrilateral has exactly one diagonal. Since a diagonal must connect two vertices that do not define an edge of the polygon, we have that a quadrilateral has exactly two distinct diagonalizations, and thus two distinct diagonal triangulations T1 and T2. As in our example above, these diagonals have to cross in the plane. By assigning the same non-zero height to the pair of vertices connected by the diagonal T1, we prevent T1 and T2 from intersecting while creating the required convex polyhedron, a tetrahedron in each case.

Dekster's Realizability Theorem:

The realizability of convex quadrilaterals is actually a special case of the realizability of a larger class of polygons and triangulations. This larger class of objects is captured by Dekster's Realizability Theorem, which gives a sufficient condition for realizability. In order to describe this theorem we will first need a few more definitions:

Definition: Given a polygon P, a diagonal D*=AB generates a triangulation T if and only if D* crosses all the diagonals in T in the order specified by the non-standard relation ≤R given below.
  • (X1 < A) and (X1 ≤ X2 < A) then X1 ≤R X2.
  • (X1 < A) and (X2 < X1 or B ≤ X2 or X2=w) then X2 ≤R X1.
  • (X1 = w) and (X2 < A or X2=w) then X1 ≤R X2.
  • (X1 = w) and (B ≤ X2 or X2=w) then X2 ≤R X1.
  • (X1 > B) and (X2 > X1 or X2 < A or X2=w) then X1 ≤R X2.
  • (X1 > B) and (B ≤ X2 < X1) then X2 ≤R X1.
where A and B are the end points of D*, w specifies the value of infinity, and Xi is the distance along the line AB where the line through an edge of P intersects the line through AB.

Theorem: Let P be a convex Polygon in general position. Let T1 and T2 be its triangulations. Suppose T2 is generated by a diagonal from T1, or T1 is generated by a diagonal from T2, then T1 and T2 are realizable.

Example: Consider the octagon shown here at the right along with the specified diagonal D*=AB. If all the diagonals in T have to cross D* then they must all be of the form PjQk. Thus we know that the diagonal P1Q1 has to be an edge in T. If it isn't, then we won't be able to obtain a complete diagonalization of the octagon using diagonals that cross D*.
The next diagonal after P1Q1 along D* is either P1Q2 or P2Q1.We decide which one to pick by computing the intercepts Pi and Qi of the lines through P2P1 and Q2Q1 with the line through AB. If we think of the line through AB as a new x-axis with 0 at A, then define d(Pi) to be the distance of Pi from A along the new x-axis, and d(Qi) to be the distance of Qi from A along the new x-axis. If d(Qi) <R d(Pi) then the next diagonal we add is Q1P2. If d(Pi) <R d(Qi) then the next diagonal we add is Q2P1.
In our case d(Pi) is less than A and d(Qi) is less than d(Pi) so d(Qi) <R d(Pi) and the next diagonal is Q1P2. Continuing on in this way we can determine all the diagonals generated by D*.

Missed Cases:

While Dekster's Theorem gives a sufficient condition for realizability, it is not a complete characterization of realizable configurations. The restriction in the hypotheses of the theorem that there must be a diagonal in T1 that crosses all the diagonals in T2 (or vice versa) is quite a severe one. In fact, we can find a simple configuration that is excluded by the conditions of Dekster's theorem, but is clearly realizable. The configuration is shown below.

McGill University School of Computer Science
Ben Marlin - 2001