Bounded-degree polyhedronization of point sets

Gill Barequet, Nadia Benbernou, David Charlton, Erik D. Demaine, Martin L. Demaine, Mashhood Ishaque, Anna Lubiw, André Schulz, Diane L. Souvaine, Godfried T. Toussaint, Andrew Winslow

Research output: Contribution to journalArticlepeer-review


In 1994 Grünbaum showed that, given a point set S in R 3, it is always possible to construct a polyhedron whose vertices are exactly S. Such a polyhedron is called a polyhedronization of S. Agarwal et al. extended this work in 2008 by showing that there always exists a polyhedronization that can be decomposed into a union of tetrahedra (tetrahedralizable). In the same work they introduced the notion of a serpentine polyhedronization for which the dual of its tetrahedralization is a chain. In this work we present a randomized algorithm running in O(n log6n) expected time which constructs a serpentine polyhedronization that has vertices with degree at most 7, answering an open question by Agarwal et al.

Original languageEnglish (US)
Pages (from-to)148-153
Number of pages6
JournalComputational Geometry: Theory and Applications
Issue number2
StatePublished - Feb 2013


  • Convex hull
  • Gift wrapping
  • Serpentine
  • Tetrahedralization

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 'Bounded-degree polyhedronization of point sets'. Together they form a unique fingerprint.

Cite this