Theorem 1

Theorem 1: Let P be a polygon in the xy-plane. Consider P', a spatial polygon obtained by assigning a z-value to each vertex of P. Let P* be the triangulated convex hull of P'. Then the projection of P* back onto the xy-plane yields two distinct triangulations of P.

Proof: First consider the fact that the convex polyhedra P* splits into two pieces in a natural way: all the faces of P* you would see while standing over it and looking down form the top P*t, and all the faces you would see while standing under it and looking up form the bottom P*b. Since P is convex, the edges of P' are contained in both P*t and P*b. If not, then with out loss of generality assume an edge of P' is not in P*t. Then it must be covered by some face of P*t, but then the projection of this face onto the xy-plane would have to contain edges outside the polygon P which can't be. Now assume we have some edge that is in both P*t and P*b and is not in P'. This can only happen if the polyhedra P* is pinched at some point, but then P* could not have been obtained from the convex hull of P'. Thus the spatial polygon P' exactly splits P* into the two pieces P*t and P*b. Now, if we separate the two pieces of P* along the boundary P' and project them back onto the horizontal plane we note first that the boundary of each is exactly the polygon P as we should expect. Also, the edges that form the triangulated convex hull of the top and bottom of P* project onto diagonals of P since they connect vertices of P'. Forming two diagonal triangularizations Tt and Tb of P. If the projection of either failed to produce a proper triangularization there would be two possible causes:

Ti is missing one or more diagonals.
Ti has two diagonals that cross.

To see why neither of these two cases can arise consider the following: If Ti is missing one or more diagonals then it must be that at least one of the faces of P* was not a triangle which contradicts the fact that P* was formed by taking the triangulated convex hull of P'. In the other case, if two diagonals that are formed from the projection of the same half of P* happen to cross, then it can't be that P* is the triangulated convex hull of P'. If we assume that the projections of two edges from the top of P* cross, then it must be that one is above the other which implies that the one that is below lies under the top of P*, but above the bottom of P*. This can only happen if the edge goes through the interior of P* which is a contradiction. On the other hand the two edges could cross and be coplanar which will not occur when forming the triamgulated convex hull.

Lastly we note that Tt and Tb can not share any diagonals. Since as noted above the only edges P*t and P*b have in common are the edges that come from P' and these are all edges of P so they can not be diagonals.

So we see that by starting with any fixed, convex polygon P in the horizontal plane, assigning each vertex some vertical variation, and then taking the convex hull of the resulting point set of vertices we obtain a convex polyhedron P*. The projection of this convex polyhedron back onto the horizontal plane yields two proper triangulations of P that must be distinct.

McGill University School of Computer Science
Ben Marlin - 2001