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

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

Computer Science

Research output: Contribution to conference › Paper › peer-review

Abstract

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 language	English (US)
Pages	99-102
Number of pages	4
State	Published - 2010
Event	22nd Annual Canadian Conference on Computational Geometry, CCCG 2010 - Winnipeg, MB, Canada Duration: Aug 9 2010 → Aug 11 2010

Other

Other	22nd Annual Canadian Conference on Computational Geometry, CCCG 2010
Country/Territory	Canada
City	Winnipeg, MB
Period	8/9/10 → 8/11/10

ASJC Scopus subject areas

Computational Mathematics
Geometry and Topology

Cite this

@conference{f31f073f066f436c8825528ff490166f,

title = "Bounded-degree polyhedronization of point sets",

abstract = "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].",

author = "Gill Barequet and Nadia Benbernou and David Charlton and Demaine, {Erik D.} and Demaine, {Martin L.} and Mashhood Ishaque and Anna Lubiw and Andr{\'e} Schulz and Souvaine, {Diane L.} and Toussaint, {Godfried T.} and Andrew Winslow",

year = "2010",

language = "English (US)",

pages = "99--102",

note = "22nd Annual Canadian Conference on Computational Geometry, CCCG 2010 ; Conference date: 09-08-2010 Through 11-08-2010",

}

TY - CONF

T1 - Bounded-degree polyhedronization of point sets

AU - Barequet, Gill

AU - Benbernou, Nadia

AU - Charlton, David

AU - Demaine, Erik D.

AU - Demaine, Martin L.

AU - Ishaque, Mashhood

AU - Lubiw, Anna

AU - Schulz, André

AU - Souvaine, Diane L.

AU - Toussaint, Godfried T.

AU - Winslow, Andrew

PY - 2010

Y1 - 2010

N2 - 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].

AB - 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].

UR - http://www.scopus.com/inward/record.url?scp=84882982643&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84882982643&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:84882982643

SP - 99

EP - 102

T2 - 22nd Annual Canadian Conference on Computational Geometry, CCCG 2010

Y2 - 9 August 2010 through 11 August 2010

ER -

Bounded-degree polyhedronization of point sets

Abstract

Other

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this