We present a new algorithm for computing the straight skeleton of a polygon. For a polygon with n vertices, among which r are reflex vertices, we give a deterministic algorithm that reduces the straight skeleton computation to a motorcycle graph computation in O(n (log n) log r) time. It improves on the previously best known algorithm for this reduction, which is randomised, and runs in expected O(n √(h+1) log² n) time for a polygon with h holes. Using known motorcycle graph algorithms, our result yields improved time bounds for computing straight skeletons. In particular, we can compute the straight skeleton of a non-degenerate polygon in O(n (log n) log r + r^(4/3 + ε)) time for any ε > 0. On degenerate input, our time bound increases to O(n (log n) log r + r^(17/11 + ε))
| Identifer | oai:union.ndltd.org:kaust.edu.sa/oai:repository.kaust.edu.sa:10754/316713 |
| Date | 06 May 2014 |
| Creators | Mencel, Liam A. |
| Contributors | Vigneron, Antoine E., Computer, Electrical and Mathematical Sciences and Engineering (CEMSE) Division, Hadwiger, Markus, Moshkov, Mikhail |
| Source Sets | King Abdullah University of Science and Technology |
| Language | English |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.0019 seconds