TY - JOUR
T1 - Straight skeletons and mitered offsets of nonconvex polytopes
AU - Aurenhammer, F.
AU - Walzl, G.
PY - 2016
Y1 - 2016
N2 - We give a concise definition of mitered offset surfaces for nonconvex polytopes in ℝ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 ℝd, an upper bound of O(nd) 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.
AB - We give a concise definition of mitered offset surfaces for nonconvex polytopes in ℝ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 ℝd, an upper bound of O(nd) 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.
KW - 3D straight skeleton
KW - Mitered offset surface
KW - Arrangement of planes
U2 - 10.1007/s00454-016-9811-5
DO - 10.1007/s00454-016-9811-5
M3 - Article
SN - 0179-5376
VL - 56
SP - 743
EP - 801
JO - Discrete & Computational Geometry
JF - Discrete & Computational Geometry
IS - 3
ER -