@inproceedings{b8e7e74ddcb34be2925ce3a887e577c7,

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(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.",

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

year = "2008",

month = aug,

day = "30",

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

language = "English",

isbn = "978-3-540-87743-1",

series = "Lecture Notes in Computer Science",

publisher = "Springer Berlin Heidelberg",

pages = "148--160",

editor = "Dan Halperin and Kurt Mehlhorn",

booktitle = "Algorithms - ESA 2008",

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

}