|
HKUST Institutional Repository >
Computer Science and Engineering >
CSE Conference Papers >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1783.1/760
|
| Title: | Motorcycle graphs and straight skelectons |
| Authors: | Cheng, Siu-Wing
Vigneron, Antoine |
| Keywords: | Motorcycle graph
Straight skelecton
Non-degenerate simple polygon
Degenerate simple polygon |
| Issue Date: | 22-Nov-2001 |
| Citation: | Proceedings of the 13th Annual ACM - SIAM Symposium on Discrete Algorithms, San Francisco, CA, Jan. 2002, ACM - Association for Computing Machinery, New York, NY, USA, 2002, p. 156-165 |
| Abstract: | We present a new algorithm to compute a motorcycle graph. It runs in O(n√n log n) time when n is the size of the input. We give a new charterization 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(n log2 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 log2 n)+r√r log r) expected time. For a degenerate simple polygon, our expected time bound becomes O(n log2 n)+r17/11+∈). |
| URI: | http://hdl.handle.net/1783.1/760 |
| Appears in Collections: | CSE Conference Papers
|
Files in This Item:
| File |
Description |
Size | Format |
|---|
| motorpub.pdf | | 264Kb | Adobe PDF | View/Open |
|
All items in this Repository are protected by copyright, with all rights reserved.
|
