Motorcycle graphs and straight skeletons

Siu Wing Cheng, Antoine Vigneron

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

17 Scopus citations


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+ϵ).

Original languageEnglish (US)
Title of host publicationProceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002
PublisherAssociation for Computing Machinery
Number of pages10
ISBN (Electronic)089871513X
StatePublished - 2002
Externally publishedYes
Event13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002 - San Francisco, United States
Duration: Jan 6 2002Jan 8 2002


Other13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002
Country/TerritoryUnited States
CitySan Francisco

ASJC Scopus subject areas

  • Software
  • Mathematics(all)


Dive into the research topics of 'Motorcycle graphs and straight skeletons'. Together they form a unique fingerprint.

Cite this