HKUST Library Institutional Repository Banner

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 SizeFormat
motorpub.pdf264KbAdobe PDFView/Open

All items in this Repository are protected by copyright, with all rights reserved.