A faster algorithm for computing straight skeletons

DOI10.1007/978-3-662-44777-2_23MaRDI QIDQ2921412zbMATH OpenOpenAlexFDO

Authors Siu-Wing Cheng, Liam Mencel, Antoine Vigneron

Publication date 8 October 2014

Published in Algorithms - ESA 2014 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1405.4691

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

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(nsqrth+1lo{g}^{2}n)$ 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+varepsilon})$ time for any $varepsilon>0$. On degenerate input, our time bound increases to $O(n(logn)logr+r^{17/11+varepsilon})$.

Recommendations

• A faster algorithm for computing straight skeletons
• Motorcycle graphs and straight skeletons
• scientific article; zbMATH DE number 2119657

Cited in

(14)

• Implementing straight skeletons with exact arithmetic: challenges and experiences
• A fast straight-skeleton algorithm based on generalized motorcycle graphs
• Straight Skeletons of Three-Dimensional Polyhedra
• Sublinear randomized algorithms for skeleton decompositions
• Straight skeletons and mitered offsets of nonconvex polytopes
• A simple algorithm for computing positively weighted straight skeletons of monotone polygons
• scientific article; zbMATH DE number 7760167 (Why is no real title available?)
• Motorcycle graphs and straight skeletons
• Fast skeleton construction
• On computing straight skeletons by means of kinetic triangulations
• Computing positively weighted straight skeletons of simple polygons based on a bisector arrangement
• scientific article; zbMATH DE number 2119657 (Why is no real title available?)
• A faster algorithm for computing straight skeletons
• Representing directed trees as straight skeletons

This page was built for publication: A faster algorithm for computing straight skeletons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2921412)