**Reference**:- Gill Barequet, Nadia Benbernou, David Charlton, Erik D. Demaine, Martin L. Demaine, Mashhood Ishaque, Anna Lubiw, André Schulz, Diane L. Souvaine, Godfried T. Toussaint, and Andrew Winslow, “Bounded-Degree Polyhedronization of Point Sets”,
*Computational Geometry: Theory and Applications*, volume 46, number 2, February 2013, pages 917–928. **Abstract**:-
In 1994 Grünbaum showed that, given a point set
*S*in ℝ^{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*log^{6}*n*) expected time that constructs a serpentine polyhedronization that has vertices with degree at most 7, answering an open question by Agarwal et al. **Availability**:- The paper is available in PDF (290k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- Polyhedronization_CCCG2010 (Bounded-Degree Polyhedronization of Point Sets)

See also other papers by Erik Demaine.

Last updated December 5, 2021 by Erik Demaine.