Paper by Erik D. Demaine

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.

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 log6 n) expected time that constructs a serpentine polyhedronization that has vertices with degree at most 7, answering an open question by Agarwal et al.

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.
These pages are generated automagically from a BibTeX file.
Last updated March 9, 2018 by Erik Demaine.