Straight skeletons of three-dimensional polyhedra

Gill Barequet; David Eppstein; Michael T. Goodrich; Amir Vaxman

doi:10.1007/978-3-540-87744-8-13

Straight skeletons of three-dimensional polyhedra

Gill Barequet^*, David Eppstein, Michael T. Goodrich, Amir Vaxman

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

We study the straight skeleton of polyhedra in 3D. We first show that the skeleton of voxel-based polyhedra may be constructed by an algorithm taking constant time per voxel. We also describe a more complex algorithm for skeletons of voxel polyhedra, which takes time proportional to the surface-area of the skeleton rather than the volume of the polyhedron. We also show that any n-vertex axis-parallel polyhedron has a straight skeleton with O(n ²) features. We provide algorithms for constructing the skeleton, which run in O( min (n ²logn,klog ^O(1) n)) time, where k is the output complexity. Next, we show that the straight skeleton of a general nonconvex polyhedron has an ambiguity, suggesting a consistent method to resolve it. We prove that the skeleton of a general polyhedron has a superquadratic complexity in the worst case. Finally, we report on an implementation of an algorithm for the general case.

Original language	English
Title of host publication	Algorithms - ESA 2008 - 16th Annual European Symposium, Proceedings
Pages	148-160
Number of pages	13
DOIs	https://doi.org/10.1007/978-3-540-87744-8-13
Publication status	Published - 24 Dec 2008
Event	16th Annual European Symposium on Algorithms, ESA 2008 - Karlsruhe, Germany Duration: 15 Sept 2008 → 17 Sept 2008

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5193 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	16th Annual European Symposium on Algorithms, ESA 2008
Country/Territory	Germany
City	Karlsruhe
Period	15/09/08 → 17/09/08

Access to Document

10.1007/978-3-540-87744-8-13

Cite this

Barequet, G., Eppstein, D., Goodrich, M. T., & Vaxman, A. (2008). Straight skeletons of three-dimensional polyhedra. In Algorithms - ESA 2008 - 16th Annual European Symposium, Proceedings (pp. 148-160). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5193 LNCS). https://doi.org/10.1007/978-3-540-87744-8-13

@inproceedings{aedf464d98454068935352b448e928fe,

title = "Straight skeletons of three-dimensional polyhedra",

abstract = "We study the straight skeleton of polyhedra in 3D. We first show that the skeleton of voxel-based polyhedra may be constructed by an algorithm taking constant time per voxel. We also describe a more complex algorithm for skeletons of voxel polyhedra, which takes time proportional to the surface-area of the skeleton rather than the volume of the polyhedron. We also show that any n-vertex axis-parallel polyhedron has a straight skeleton with O(n 2) features. We provide algorithms for constructing the skeleton, which run in O( min (n 2logn,klog O(1) n)) time, where k is the output complexity. Next, we show that the straight skeleton of a general nonconvex polyhedron has an ambiguity, suggesting a consistent method to resolve it. We prove that the skeleton of a general polyhedron has a superquadratic complexity in the worst case. Finally, we report on an implementation of an algorithm for the general case.",

author = "Gill Barequet and David Eppstein and Goodrich, {Michael T.} and Amir Vaxman",

year = "2008",

month = dec,

day = "24",

doi = "10.1007/978-3-540-87744-8-13",

language = "English",

isbn = "3540877436",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "148--160",

booktitle = "Algorithms - ESA 2008 - 16th Annual European Symposium, Proceedings",

note = "16th Annual European Symposium on Algorithms, ESA 2008 ; Conference date: 15-09-2008 Through 17-09-2008",

}

Barequet, G, Eppstein, D, Goodrich, MT & Vaxman, A 2008, Straight skeletons of three-dimensional polyhedra. in Algorithms - ESA 2008 - 16th Annual European Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5193 LNCS, pp. 148-160, 16th Annual European Symposium on Algorithms, ESA 2008, Karlsruhe, Germany, 15/09/08. https://doi.org/10.1007/978-3-540-87744-8-13

Straight skeletons of three-dimensional polyhedra. / Barequet, Gill; Eppstein, David; Goodrich, Michael T. et al.
Algorithms - ESA 2008 - 16th Annual European Symposium, Proceedings. 2008. p. 148-160 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5193 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Straight skeletons of three-dimensional polyhedra

AU - Barequet, Gill

AU - Eppstein, David

AU - Goodrich, Michael T.

AU - Vaxman, Amir

PY - 2008/12/24

Y1 - 2008/12/24

N2 - We study the straight skeleton of polyhedra in 3D. We first show that the skeleton of voxel-based polyhedra may be constructed by an algorithm taking constant time per voxel. We also describe a more complex algorithm for skeletons of voxel polyhedra, which takes time proportional to the surface-area of the skeleton rather than the volume of the polyhedron. We also show that any n-vertex axis-parallel polyhedron has a straight skeleton with O(n 2) features. We provide algorithms for constructing the skeleton, which run in O( min (n 2logn,klog O(1) n)) time, where k is the output complexity. Next, we show that the straight skeleton of a general nonconvex polyhedron has an ambiguity, suggesting a consistent method to resolve it. We prove that the skeleton of a general polyhedron has a superquadratic complexity in the worst case. Finally, we report on an implementation of an algorithm for the general case.

AB - We study the straight skeleton of polyhedra in 3D. We first show that the skeleton of voxel-based polyhedra may be constructed by an algorithm taking constant time per voxel. We also describe a more complex algorithm for skeletons of voxel polyhedra, which takes time proportional to the surface-area of the skeleton rather than the volume of the polyhedron. We also show that any n-vertex axis-parallel polyhedron has a straight skeleton with O(n 2) features. We provide algorithms for constructing the skeleton, which run in O( min (n 2logn,klog O(1) n)) time, where k is the output complexity. Next, we show that the straight skeleton of a general nonconvex polyhedron has an ambiguity, suggesting a consistent method to resolve it. We prove that the skeleton of a general polyhedron has a superquadratic complexity in the worst case. Finally, we report on an implementation of an algorithm for the general case.

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

U2 - 10.1007/978-3-540-87744-8-13

DO - 10.1007/978-3-540-87744-8-13

M3 - Conference contribution

AN - SCOPUS:57749188194

SN - 3540877436

SN - 9783540877431

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 148

EP - 160

BT - Algorithms - ESA 2008 - 16th Annual European Symposium, Proceedings

T2 - 16th Annual European Symposium on Algorithms, ESA 2008

Y2 - 15 September 2008 through 17 September 2008

ER -

Straight skeletons of three-dimensional polyhedra

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this