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)