Hauptmenü
• Autor
• Aurenhammer, Franz
• Walzl, Gernot Christian
• TitelStraight skeletons and mitered offsets of nonconvex polytopes
• Datei
• DOI10.1007/s00454-016-9811-5
• Persistent Identifier
• Erschienen inDiscrete & computational geometry
• Band56
• Erscheinungsjahr2016
• Heft3
• Seiten743-801
• LicenceCC-BY
• Zugriffsrechte
• AbstractWe give a concise definition of mitered offset surfaces for nonconvex polytopes in $$\mathbb{R}^3$$, along with a proof of existence and a discussion of basic properties. These results imply the existence of 3D straight skeletons for general nonconvex polytopes. The geometric, topological, and algorithmic features of such skeletons are investigated, including a classification of their constructing events in the generic case. Our results extend to the weighted setting, to a larger class of polytope decompositions, and to general dimensions. For (weighted) straight skeletons of an n-facet polytope in $$\mathbb{R}^d$$, an upper bound of $$O(n^d)$$ on their combinatorial complexity is derived. It relies on a novel layer partition for straight skeletons, and improves the trivial bound by an order of magnitude for d ≥ 3.