A Faster Algorithm for Computing Motorcycle Graphs

Antoine E. Vigneron*, Lie Yan

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

We present a new algorithm for computing motorcycle graphs that runs in (Formula presented.) time for any (Formula presented.), improving on all previously known algorithms. The main application of this result is to computing the straight skeleton of a polygon. It allows us to compute the straight skeleton of a non-degenerate polygon with (Formula presented.) holes in (Formula presented.) expected time. If all input coordinates are (Formula presented.)-bit rational numbers, we can compute the straight skeleton of a (possibly degenerate) polygon with (Formula presented.) holes in (Formula presented.) expected time. In particular, it means that we can compute the straight skeleton of a simple polygon in (Formula presented.) expected time if all input coordinates are (Formula presented.)-bit rationals, while all previously known algorithms have worst-case running time (Formula presented.). © 2014 Springer Science+Business Media New York.
Original languageEnglish (US)
Pages (from-to)492-514
Number of pages23
JournalDiscrete & Computational Geometry
Volume52
Issue number3
DOIs
StatePublished - Aug 29 2014

Fingerprint Dive into the research topics of 'A Faster Algorithm for Computing Motorcycle Graphs'. Together they form a unique fingerprint.

Cite this