TY - GEN

T1 - A Faster Algorithm for Computing Straight Skeletons

AU - Cheng, Siu-Wing

AU - Mencel, Liam A.

AU - Vigneron, Antoine E.

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

PY - 2014/8/16

Y1 - 2014/8/16

N2 - We present a new algorithm for computing the straight skeleton of a polygon. For a polygon with n vertices, among which r are reflex vertices, we give a deterministic algorithm that reduces the straight skeleton computation to a motorcycle graph computation in O(n (logn)logr) time. It improves on the previously best known algorithm for this reduction, which is randomized, and runs in expected O(n√h+1log2n) time for a polygon with h holes. Using known motorcycle graph algorithms, our result yields improved time bounds for computing straight skeletons. In particular, we can compute the straight skeleton of a non-degenerate polygon in O(n (logn) logr + r 4/3 + ε ) time for any ε > 0. On degenerate input, our time bound increases to O(n (logn) logr + r 17/11 + ε ).

AB - We present a new algorithm for computing the straight skeleton of a polygon. For a polygon with n vertices, among which r are reflex vertices, we give a deterministic algorithm that reduces the straight skeleton computation to a motorcycle graph computation in O(n (logn)logr) time. It improves on the previously best known algorithm for this reduction, which is randomized, and runs in expected O(n√h+1log2n) time for a polygon with h holes. Using known motorcycle graph algorithms, our result yields improved time bounds for computing straight skeletons. In particular, we can compute the straight skeleton of a non-degenerate polygon in O(n (logn) logr + r 4/3 + ε ) time for any ε > 0. On degenerate input, our time bound increases to O(n (logn) logr + r 17/11 + ε ).

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

UR - http://link.springer.com/chapter/10.1007/978-3-662-44777-2_23

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

U2 - 10.1007/978-3-662-44777-2_23

DO - 10.1007/978-3-662-44777-2_23

M3 - Conference contribution

SN - 9783662447765

SP - 272

EP - 283

BT - Lecture Notes in Computer Science

PB - Springer Science + Business Media

ER -