Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/760

Motorcycle graphs and straight skeletons

Authors Cheng, SW
Vigneron, A
Issue Date 2002
Source PROCEEDINGS OF THE THIRTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS , 2002, p. 156-165
Summary We present a new algorithm to compute a motorcycle graph. It runs in O(nrootn 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 0(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 + rrootr log r) expected time. For a degenerate simple polygon, our expected time bound becomes O(n log(2) n + r (17/11+epsilon)).
Subjects
Language English
Format Conference paper
Access View full-text via Web of Science
Files in this item:
File Description Size Format
motorpub.pdf 271014 B Adobe PDF