Abstract
We present a new algorithm to compute a motorcycle graph. It runs in O ( n √ n log n ) time when n is the size of the input. We give a new characterization of the straight skeleton of a polygon possibly with holes. For a simple polygon, we show that it yields a randomized algorithm that reduces the straight skeleton computation to a motorcycle graph computation in O ( n log 2 n ) time. Combining these results, we can compute the straight skeleton of a non-degenerate simple polygon with n vertices, among which r are reflex vertices, in O ( n log 2 n + r √ r log r ) expected time. For a degenerate simple polygon, our expected time bound becomes O ( n log 2 n + r 17/11+ε ).