Straight Skeletons of Three-Dimensional Polyhedra - Computer Science > Computational GeometryReportar como inadecuado

Straight Skeletons of Three-Dimensional Polyhedra - Computer Science > Computational Geometry - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: This paper studies the straight skeleton of polyhedra in three dimensions. Wefirst address voxel-based polyhedra polycubes, formed as the union of acollection of cubical axis-aligned voxels. We analyze the ways in which theskeleton may intersect each voxel of the polyhedron, and show that the skeletonmay be constructed by a simple voxel-sweeping algorithm taking constant timeper voxel. In addition, we describe a more complex algorithm for straightskeletons of voxel-based polyhedra, which takes time proportional to the areaof the surfaces of the straight skeleton rather than the volume of thepolyhedron. We also consider more general polyhedra with axis-parallel edgesand faces, and show that any n-vertex polyhedron of this type has a straightskeleton with On^2 features. We provide algorithms for constructing thestraight skeleton, with running time Ominn^2 log n, k log^{O1} n where kis the output complexity. Next, we discuss the straight skeleton of a generalnonconvex polyhedron. We show that it has an ambiguity issue, and suggest aconsistent method to resolve it. We prove that the straight skeleton of ageneral polyhedron has a superquadratic complexity in the worst case. Finally,we report on an implementation of a simple algorithm for the general case.

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


Documentos relacionados