Straight Skeletons of Three-Dimensional Polyhedra

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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(n2) features. We provide algorithms for constructing the skeleton, which run in O( min (n2logn,klogO(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 languageEnglish
Title of host publicationAlgorithms - ESA 2008
Subtitle of host publication16th Annual European Symposium, Karlsruhe, Germany, September 15-17, 2008, Proceedings
EditorsDan Halperin, Kurt Mehlhorn
Place of PublicationBerlin, Heidelberg
PublisherSpringer
Pages148-160
Number of pages13
ISBN (Electronic)978-3-540-87744-8
ISBN (Print)978-3-540-87743-1
DOIs
Publication statusPublished - 30 Aug 2008
EventEuropean Symposium on Algorithms 2008 - Karlsruhe, Germany
Duration: 15 Sept 200817 Sept 2008

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin, Heidelberg
Volume5193
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Symposium

SymposiumEuropean Symposium on Algorithms 2008
Abbreviated titleESA 2008
Country/TerritoryGermany
CityKarlsruhe
Period15/09/0817/09/08

Fingerprint

Dive into the research topics of 'Straight Skeletons of Three-Dimensional Polyhedra'. Together they form a unique fingerprint.

Cite this