Computational Geometry

Marlin, Benjamin, and Godfried Toussaint. "Constructing convex 3-polytopes from two triangulations of a polygon." Computational Geometry. 28 (2004): 41-47. AbstractDownload Paper

Guibas conjectured that given a convex polygon P in the xy-plane along with two triangulations of it, T1 and T2 that share no diagonals, it is always possible to assign height values to the vertices of P such that P∪T1∪T2 becomes a convex 3-polytope. Dekster found a counter example but left open the questions of deciding if a given configuration corresponds to a convex 3-polytope, and constructing such realizations when they exist. This paper presents a characterization of realizable configurations for Guibas' conjecture based on work from the area of polytope convexity testing. Our approach to the decision and construction problems is a reduction to a linear-inequality feasibility problem. The approach is also related to methods used for deciding if an arbitrary triangulation of a point set is a regular triangulation. We show two reductions, one based directly on a global convexity condition resulting in number of inequalities that is quadratic in the number of vertices of P, and one based on an equivalent local convexity condition resulting in a linear number of inequalities.

Marlin, Benjamin M., and Godfried T. Toussaint. "Constructing convex 3-polytopes from two triangulations of a polygon." CCCG. 2002. 36-39. Abstract

Guibas conjectured that given a convex polygon P in the xy-plane along with two triangulations of it, T1 and T2 that share no diagonals, it is always possible to assign height values to the vertices of P such that P U T1 U T 2 becomes a convex 3-polytope. Dekster found a counter example but left open the questions of deciding if a given configuration 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.