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 -