Dekster's Counter Example
Dekster's Counter Example:
Dekster proves a general theorem about the properties a triangulation must have in order to produce a convex polyhedron. He then presents an example where these properties don't hold and concludes that Guibas' conjecture is, in fact, false. The proof of this theorem is quite difficult so instead of presenting it in a general form, it has been adapted to the specific counter example presented by Dekster, which is pictured below. By interpreting Dekster's proof in the context of a fixed counter example the result can be seen much more directly. The construction is still quite complex, so a new figure is provided at each stage of the proof. Clicking on the title of any figure will display an enlarged version for easier viewing.
Proof:
Capital letters will denote the projection onto the xy-plane of points and lines in three dimensions. The notation [ijk] will be used to denote the plane of three vertices i,j,k.
First we construct two lines: let L be the line through AD, and M be the line through BE. Now, construct a ray starting at C and passing though D. It intersects M at a point we'll call Z. Denote by X the point of intersection of AD and BE as seen in Figure 1.
|
Figure 1
|
|
Denote by h the intersection of the two planes [afe] and
[bcd]. Since these planes contain
two faces of the bottom and are "hinged" along the bottom edges ae and bd that project onto parallel lines, the projection of the line h onto the plane forms a line H that must intersect both the segment AB and the segment ED. The line H is pictured here with an arbitrary placement. Since H crosses AB and ED it crosses the interior of the quadrilateral ABDE thus it must also cross BE and DZ. Denote by G the point of intersection of H with DZ and note that whatever the exact placement of H the inequality |DG|<|DZ| will always hold. This can be seen in Figure 2.
|
Figure 2
|
|
Since G is between Z and D it is always possible to find a
point W that lies on the segment AG and is in the interior of the quadrilateral
AXEF. The segment WC must then intersect the diagonal AD at a point Y that is
inside the polygon (see Figure 3). Denote by w1 the point contained in the plane
[aef] having projection W. Since [aef] is the plane of a face of the bottom of P*
and W is in the interior of P it must be that w1 is on or below the bottom of P*. Let w2 be any point in the interior of P* also having projection W, then w2 is above w1. Also consider the point y1 on the segment w1c and the point y2 on the segment w2c both having projection Y. Since w2 is above w1 it must be that y2 is above y1.
|
Figure 3
|
|
Finally we derive a contradiction as follows: Let g be the point of [aef] having projection G. By the above construction g lies in [bcd] as well since g is on the line h, which is the intersection of the planes [aef] and [bcd] by definition. Then d lies on the segment gc. Since w1 lies on ga by definition and d lies on gc we have that w1c, and ad cross at y1. y1 is then an element of the top of P*, so y2 can not be above y1 since y1 is in the interior of P*. This contradicts the above assertion that y2 is above y1. Thus these two triangulations have no realization as a convex polyhedron and Guibas' conjecture is false.
|
|