TY - JOUR

T1 - A Faster Algorithm for Computing Motorcycle Graphs

AU - Vigneron, Antoine E.

AU - Yan, Lie

N1 - KAUST Repository Item: Exported on 2020-10-01

PY - 2014/8/29

Y1 - 2014/8/29

N2 - 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.

AB - 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.

UR - http://hdl.handle.net/10754/348466

UR - http://link.springer.com/10.1007/s00454-014-9625-2

UR - http://www.scopus.com/inward/record.url?scp=85027953958&partnerID=8YFLogxK

U2 - 10.1007/s00454-014-9625-2

DO - 10.1007/s00454-014-9625-2

M3 - Article

SN - 0179-5376

VL - 52

SP - 492

EP - 514

JO - Discrete & Computational Geometry

JF - Discrete & Computational Geometry

IS - 3

ER -