Computer Science – Computational Geometry
Scientific paper
2008-04-30
Computer Science
Computational Geometry
12 pages, 47 figure files in 8 figures
Scientific paper
This paper studies the straight skeleton of polyhedra in three dimensions. We first address voxel-based polyhedra (polycubes), formed as the union of a collection of cubical (axis-aligned) voxels. We analyze the ways in which the skeleton may intersect each voxel of the polyhedron, and show that the skeleton may be constructed by a simple voxel-sweeping algorithm taking constant time per voxel. In addition, we describe a more complex algorithm for straight skeletons of voxel-based polyhedra, which takes time proportional to the area of the surfaces of the straight skeleton rather than the volume of the polyhedron. We also consider more general polyhedra with axis-parallel edges and faces, and show that any n-vertex polyhedron of this type has a straight skeleton with O(n^2) features. We provide algorithms for constructing the straight skeleton, with running time O(min(n^2 log n, k log^{O(1)} n)) where k is the output complexity. Next, we discuss the straight skeleton of a general nonconvex polyhedron. We show that it has an ambiguity issue, and suggest a consistent method to resolve it. We prove that the straight skeleton of a general polyhedron has a superquadratic complexity in the worst case. Finally, we report on an implementation of a simple algorithm for the general case.
Barequet Gill
Eppstein David
Goodrich Michael T.
Vaxman Amir
No associations
LandOfFree
Straight Skeletons of Three-Dimensional Polyhedra does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Straight Skeletons of Three-Dimensional Polyhedra, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Straight Skeletons of Three-Dimensional Polyhedra will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-40761