Faster Reductions for Straight Skeletons to Motorcycle Graphs

Abstract

We give an algorithm that reduces the straight skeleton to the motorcycle graph in $O(n\log n)$ time for simple polygons and $O(n(\log n)\log m)$ time for a planar straight line graph (PSLG) with $m$ connected components. This improves on the previous best of $O(n(\log n)\log r)$ for polygons with $r$ reflex vertices (possibly with holes) and $O(n^2\log n)$ for general planar straight line graphs. This allows us to speed up the straight skeleton algorithm for polygons and PSLGs. For a polygon with $h$ holes and $r$ reflex vertices we achieve a speedup from $O(n(\log n)\log r+r^{4/3+\epsilon })$ time to $O(n(\log n)\log h+r^{4/3+\epsilon })$ time in the non-degenerate case and from $O(n(\log n)\log r+r^{17/11+\epsilon })$ to $O(n(\log n)\log h+r^{17/11+\epsilon })$ in degenerate cases. For a PSLG with $m$ connected components and $r$ reflex vertices, we gain a speed up from $O(n^{1+\epsilon }+n^{8/11+\epsilon }{r}^{9/11+\epsilon })$ to $O(n(\log n)\log m+r^{4/3+\epsilon })$ in the non-degenerate case and from $O(n^{1+\epsilon }+n^{8/11+\epsilon }{r}^{9/11+\epsilon })$ to $O(n(\log n)\log m+r^{17/11+\epsilon })$ in the degenerate case.

arXiv commentFixed typos from V3