@inproceedings{f133e2bf9fe7437c9c04e9cb0512e1e4,
title = "Motorcycle graphs and straight skeletons",
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+ϵ).",
author = "Cheng, {Siu Wing} and Antoine Vigneron",
year = "2002",
language = "English (US)",
series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",
publisher = "Association for Computing Machinery",
pages = "156--165",
booktitle = "Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002",
note = "13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002 ; Conference date: 06-01-2002 Through 08-01-2002",
}