Constructing Convex 3-Polytopes from Two Triangulations of a Polygon

Guibas conjectured that given a convex polygon P in the xy-plane along with two triangulations of it, T 1 and T 2 that share no diagonals, it is always possible to assign height values to the vertices of P such that P [T 1 [T 2 becomes a convex 3-polytope. Dekster found a counter example but left open the questions of deciding if a given con guration corresponds to a convex 3-polytope, and constructing such realizations when they exist. This paper gives a proof that a relaxed version of Guibas' conjecture always holds true. The question of deciding the realizability of Guibas' conjecture is characterized in terms of a linear programming problem. This leads to an algorithm for deciding and constructing such realizations that incorporates a linear programming step with O(n ) inequality constraints and n variables.