Motorcycle graphs and straight skeletons

Siu Wing Cheng, Antoine Vigneron

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

15 Scopus citations

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

Original languageEnglish (US)
Title of host publicationProceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002
PublisherAssociation for Computing Machinery
Pages156-165
Number of pages10
Volume06-08-January-2002
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

Other

Other13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002
CountryUnited States
CitySan Francisco
Period01/6/0201/8/02

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

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

Cite this