A faster algorithm for computing motorcycle graphs

Antoine Vigneron, Lie Yan

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

10 Scopus citations

Abstract

We present a new algorithm for computing motorcycle graphs that runs in O(n4/3+ε) time for any ε > 0, 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 h holes in O(n√h+1 log 2 n + n4/3+ε) expected time. If all input coordinates are O(logn)-bit rational numbers, we can compute the straight skeleton of a (possibly degenerate) polygon with h holes in expected time O(n√h+1 log3n). In particular, it means that we can compute the straight skeleton of a simple polygon in O(nlog3n) expected time if all input coordinates are O(log n)-bit rationals, while all previously known algorithms have worst-case running time ω(n3/2).

Original languageEnglish (US)
Title of host publicationProceedings of the 29th Annual Symposium on Computational Geometry, SoCG 2013
PublisherAssociation for Computing Machinery
Pages17-26
Number of pages10
ISBN (Print)9781450320313
DOIs
StatePublished - Jan 1 2013
Event29th Annual Symposium on Computational Geometry, SoCG 2013 - Rio de Janeiro, Brazil
Duration: Jun 17 2013Jun 20 2013

Publication series

NameProceedings of the Annual Symposium on Computational Geometry

Other

Other29th Annual Symposium on Computational Geometry, SoCG 2013
CountryBrazil
CityRio de Janeiro
Period06/17/1306/20/13

Keywords

  • Algorithms design and analysis
  • Computational geometry
  • Straight skeleton

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Fingerprint Dive into the research topics of 'A faster algorithm for computing motorcycle graphs'. Together they form a unique fingerprint.

Cite this