A Faster Algorithm for Computing Straight Skeletons
Siu-Wing Cheng, Liam Mencel, Antoine Vigneron · ACM Transactions on Algorithms · 2016
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 nondegenerate polygon in O ( n (log n )log r + r 4/3 + ε ) time for any ε > 0. On degenerate input, our time bound increases to O ( n (log n )log r + r 17/11 + ε ).