Hauptmenü
  • Autor
    • Aurenhammer, Franz
    • Walzl, Gernot
  • 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
  • ISSN1432-0444
  • ZugriffsrechteCC-BY
  • Download Statistik354
  • Peer ReviewNein
  • 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 \ge 3\).