A Faster Algorithm for Computing Straight Skeletons

DOI10.1145/2898961zbMath1423.68542OpenAlexW73899363MaRDI QIDQ4962620

Liam Mencel, Antoine Vigneron, Siu-Wing Cheng

Publication date: 5 November 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2898961

zbMATH Keywords

straight skeletonmotorcycle graph

Mathematics Subject Classification ID

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

Related Items (6)

Computing positively weighted straight skeletons of simple polygons based on a bisector arrangement ⋮ Emanation graph: a plane geometric spanner with Steiner points ⋮ Min-/Max-Volume Roofs Induced by Bisector Graphs of Polygonal Footprints of Buildings ⋮ Implementing straight skeletons with exact arithmetic: challenges and experiences ⋮ Convex-straight-skeleton Voronoi diagrams for segments and convex polygons ⋮ Recognizing Geometric Trees as Positively Weighted Straight Skeletons and Reconstructing Their Input

This page was built for publication: A Faster Algorithm for Computing Straight Skeletons