@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",
pages = "148--160",
editor = "Dan Halperin and Kurt Mehlhorn",
booktitle = "Algorithms - ESA 2008",
address = "United Kingdom",
note = "European Symposium on Algorithms 2008, ESA 2008 ; Conference date: 15-09-2008 Through 17-09-2008",
}