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'.
Intuition:
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:
|