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
Last updated January 15, 2021 by