Abstract
We present a new algorithm to compute a motorcycle graph. It runs in O(n√nlogn) 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(nlog2n) 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(nlog2n + r√logr) expected time. For a degenerate simple polygon, our expected time bound becomes O(nlog2n + r17/u+ϵ).
Original language | English (US) |
---|---|
Title of host publication | Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002 |
Publisher | Association for Computing Machinery |
Pages | 156-165 |
Number of pages | 10 |
Volume | 06-08-January-2002 |
ISBN (Electronic) | 089871513X |
State | Published - 2002 |
Externally published | Yes |
Event | 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002 - San Francisco, United States Duration: Jan 6 2002 → Jan 8 2002 |
Other
Other | 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002 |
---|---|
Country/Territory | United States |
City | San Francisco |
Period | 01/6/02 → 01/8/02 |
ASJC Scopus subject areas
- Software
- Mathematics(all)