Constructing convex 3-polytopes from two triangulations of a polygon

Benjamin Marlin, Godfried Toussaint

Research output: Contribution to journalArticlepeer-review


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 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.

Original languageEnglish (US)
Pages (from-to)41-47
Number of pages7
JournalComputational Geometry: Theory and Applications
Issue number1
StatePublished - May 2004


  • Computational geometry
  • Convex polytopes
  • Convexity theory
  • Graph drawing
  • Linear programming
  • Projections
  • Realizations
  • Triangulations

ASJC Scopus subject areas

  • Computer Science Applications
  • Geometry and Topology
  • Control and Optimization
  • Computational Theory and Mathematics
  • Computational Mathematics


Dive into the research topics of 'Constructing convex 3-polytopes from two triangulations of a polygon'. Together they form a unique fingerprint.

Cite this