Abstract
We present a new algorithm to compute motorcycle graphs. It runs in o(n√nlogn) 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+1log²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+1log²n+r√rlogr) expected time. In particular, we cancompute the straight skeleton of a nondegenerate polygon with n vertices in o(n√nlog²n)expected time