Motorcycle graphs and straight skeletons

We present a new algorithm to compute motorcycle graphs. It runs in O(n √n log n) time when n is the number of motorcycles. We give a new characterization of the straight skeleton of a nondegenerate polygon. For a polygon with n vertices and h holes, we show that it yields a randomized algorithm that reduces the straight skeleton computation to a motorcycle graph computation in expected O(n√h+1 log ² n) time. Combining these results, we can compute the straight skeleton of a nondegenerate polygon with h holes and with n vertices, among which r are reflex vertices, in O(n√h+1 log ² n + r √r log r)expected time. In particular, we cancompute the straight skeleton of a nondegenerate polygon with n vertices in O(n√nlog ² n expected time.