License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2020.38
URN: urn:nbn:de:0030-drops-121964
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12196/
Eder, Günther ;
Held, Martin ;
Palfrader, Peter
On Implementing Straight Skeletons: Challenges and Experiences
Abstract
We present Cgal implementations of two algorithms for computing straight skeletons in the plane, based on exact arithmetic. One code, named Surfer2, can handle multiplicatively weighted planar straight-line graphs (PSLGs) while our second code, Monos, is specifically targeted at monotone polygons. Both codes are available on GitHub. We discuss algorithmic as well as implementational and engineering details of both codes. Furthermore, we present the results of an extensive performance evaluation in which we compared Surfer2 and Monos to the straight-skeleton package included in Cgal. It is not surprising that our special-purpose code Monos outperforms Cgal’s straight-skeleton implementation. But our tests provide ample evidence that also Surfer2 can be expected to be faster and to consume significantly less memory than the Cgal code. And, of course, Surfer2 is more versatile because it can handle multiplicative weights and general PSLGs as input. Thus, Surfer2 currently is the fastest and most general straight-skeleton code available.
BibTeX - Entry
@InProceedings{eder_et_al:LIPIcs:2020:12196,
author = {G{\"u}nther Eder and Martin Held and Peter Palfrader},
title = {{On Implementing Straight Skeletons: Challenges and Experiences}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {38:1--38:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Sergio Cabello and Danny Z. Chen},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12196},
URN = {urn:nbn:de:0030-drops-121964},
doi = {10.4230/LIPIcs.SoCG.2020.38},
annote = {Keywords: weighted straight skeleton, implementation, algorithm engineering, experiments, Cgal, Core}
}
