A Faster Algorithm for Computing Straight Skeletons

Siu-Wing Cheng, Liam A. Mencel, Antoine E. Vigneron

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

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 + ε ).
Original languageEnglish (US)
Title of host publicationLecture Notes in Computer Science
PublisherSpringer Science + Business Media
Pages272-283
Number of pages12
ISBN (Print)9783662447765
DOIs
StatePublished - Aug 16 2014

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

Cite this