Paper by Erik D. Demaine

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.

BibTeX

@Article{Polyhedronization_CGTA,
  AUTHOR        = {Gill Barequet and Nadia Benbernou and David Charlton and Erik D. Demaine and Martin L. Demaine and Mashhood Ishaque and Anna Lubiw and Andr\'e Schulz and Diane L. Souvaine and Godfried T. Toussaint and Andrew Winslow},
  TITLE         = {Bounded-Degree Polyhedronization of Point Sets},
  JOURNAL       = {Computational Geometry: Theory and Applications},
  journalurl    = {https://www.sciencedirect.com/journal/computational-geometry},
  VOLUME        = 46,
  NUMBER        = 2,
  MONTH         = {February},
  YEAR          = 2013,
  PAGES         = {917--928},

  withstudent   = 1,
  replaces      = {Polyhedronization_CCCG2010},
  papers        = {Polyhedronization_CCCG2010},
  doi           = {https://dx.doi.org/10.1016/J.COMGEO.2012.02.008},
  dblp          = {https://dblp.org/rec/journals/comgeo/BarequetBCDDILSSTW13},
  comments      = {This paper is also available from <A HREF="https://doi.org/10.1016/j.comgeo.2012.02.008">ScienceDirect</A>.},
}

Abstract:

In 1994 Grünbaum showed that, given a point set S in ℝ³, 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⁶ n) expected time that constructs a serpentine polyhedronization that has vertices with degree at most 7, answering an open question by Agarwal et al.

Comments:

This paper is also available from ScienceDirect.

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)