A Faster Algorithm for Computing Straight Skeletons

Abstract

We present a new algorithm for computing the straight skeleton of a polygon. For a polygon with $n$ vertices, among which $r$ are reflex vertices, we give a deterministic algorithm that reduces the straight skeleton computation to a motorcycle graph computation in $O(n(\log n)\log r)$ time. It improves on the previously best known algorithm for this reduction, which is randomized, and runs in expected $O(n\sqrt{h+1}{\log }^{2}n)$ time for a polygon with $h$ holes. Using known motorcycle graph algorithms, our result yields improved time bounds for computing straight skeletons. In particular, we can compute the straight skeleton of a non-degenerate polygon in $O(n(\log n)\log r+r^{4/3+\epsilon })$ time for any $\epsilon >0$. On degenerate input, our time bound increases to $O(n(\log n)\log r+r^{17/11+\epsilon })$.