Faster Reductions for Straight Skeletons to Motorcycle Graphs

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\mathrm{/}3+ϵ})$ time to $O(n(\log n)\log h+r^{4\mathrm{/}3+ϵ})$ time in the non-degenerate case and from $O(n(\log n)\log r+r^{17\mathrm{/}11+ϵ})$ to $O(n(\log n)\log h + r^{17/11 + \epsilon})$indegeneratecases\mathrm{.}ForaPSLGwith$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})$inthenon-degeneratecaseandfrom$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.