Constructing convex 3-polytopes from two triangulations of a polygon (Q598553)

This paper deals with the following problem: Given a convex polygon \(P\) in the \(xy\)-plane and two triangulations of \(P\), \(T_1\) and \(T_2\), that share no diagonals, assign height values to the vertices of \(P\), such that \(P\cup T_1\cup T_2\) becomes a convex polytope. Guibas conjectured this was possible for any \(P,T_1,T_2\), but Dekster gave a counterexample. In this paper, a characterization is given for the configurations that are realizable, related to work from the area of convexity testing. This leads to an algorithm for deciding whether \(P,T_1,T_2\) has a realization as a polytope, based on deciding the feasibibilty of a set of linear inequalities.