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 conferencePaperpeer-review


In 1994 Grunbaum [2] showed, given a point set S in R3, that 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. [1] extended this work in 2008 by showing that a polyhedronization always exists that is decomposable 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 an algorithm for constructing a serpentine polyhedronization that has vertices with bounded degree of 7, answering an open question by Agarwal et al. [1].

Original languageEnglish (US)
Number of pages4
StatePublished - 2010
Event22nd Annual Canadian Conference on Computational Geometry, CCCG 2010 - Winnipeg, MB, Canada
Duration: Aug 9 2010Aug 11 2010


Other22nd Annual Canadian Conference on Computational Geometry, CCCG 2010
CityWinnipeg, MB

ASJC Scopus subject areas

  • Computational Mathematics
  • Geometry and Topology


Dive into the research topics of 'Bounded-degree polyhedronization of point sets'. Together they form a unique fingerprint.

Cite this