Abstract
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 2 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 2 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 2 n expected time.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 159-182 |
| Number of pages | 24 |
| Journal | Algorithmica (New York) |
| Volume | 47 |
| Issue number | 2 |
| DOIs | |
| State | Published - Feb 2007 |
| Externally published | Yes |
Bibliographical note
Funding Information:We thank Denise Zickler and Philippe Silar for helpful comments on the manuscript, Catherine Gerlinger for technical assistance, and Donal O’Sullivan for editing the English text. This work was supported by grants from the CNRS (UMR 8621), the University Paris IX. J. M. Davière was supported by a grant of the Ministère de l’Enseignement Supérieur et de la Recherche.
Keywords
- Computational geometry
- Medical axis
- Motorcycle graph
- Randomized algorithm
- Straight skeleton
ASJC Scopus subject areas
- General Computer Science
- Computer Science Applications
- Applied Mathematics