LIPIcs.SoCG.2020.76.pdf
- Filesize: 456 kB
- 4 pages
Document
Step-By-Step Straight Skeletons (Media Exposition)
Authors
Günther Eder 
,
Martin Held ,
Peter Palfrader
-
Part of:
Volume:
36th International Symposium on Computational Geometry (SoCG 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-06-08
File
Document Identifiers
Author Details
Cite As Get BibTex
Günther Eder, Martin Held, and Peter Palfrader. Step-By-Step Straight Skeletons (Media Exposition). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 76:1-76:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.SoCG.2020.76
Abstract
We present two software packages for computing straight skeletons: Monos, our implementation of an algorithm by Biedl et al. (2015), computes the straight skeleton of a monotone input polygon, and Surfer2 implements a generalization of an algorithm by Aichholzer and Aurenhammer (1998) to handle multiplicatively-weighted planar straight-line graphs as input. The graphical user interfaces that ship with our codes support step-by-step computations, where each event can be investigated and studied by the user. This makes them a canonical candidate for educational purposes and detailed event analyses. Both codes are freely available on GitHub.
Subject Classification
ACM Subject Classification
- Theory of computation → Computational geometry
Keywords
- weighted straight skeleton
- implementation
- visualization
- graphical user interface
- education
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Oswin Aichholzer and Franz Aurenhammer. Straight Skeletons for General Polygonal Figures in the Plane. In Voronoi’s Impact on Modern Sciences II, volume 21, pages 7-21. Institute of Mathematics of the National Academy of Sciences of Ukraine, 1998. URL: https://doi.org/10.1007/3-540-61332-3_144.
- Oswin Aichholzer, Franz Aurenhammer, David Alberts, and Bernd Gärtner. A Novel Type of Skeleton for Polygons. Journal of Universal Computer Science, 1(12):752-761, 1995. URL: https://doi.org/10.1007/978-3-642-80350-5_65.
- Therese Biedl, Martin Held, Stefan Huber, Dominik Kaaser, and Peter Palfrader. A Simple Algorithm for Computing Positively Weighted Straight Skeletons of Monotone Polygons. Information Processing Letters, 115(2):243-247, 2015. URL: https://doi.org/10.1016/j.ipl.2014.09.021.
-
Günther Eder, Martin Held, and Peter Palfrader. On Implementing Straight Skeletons: Challenges and Experiences. In 36th International Symposium on Computational Geometry, SoCG 2020, volume 164 of LIPIcs, pages 38:1-38:16, Zürich, Switzerland, 2020.
- David Eppstein and Jeff Erickson. Raising Roofs, Crashing Cycles, and Playing Pool: Applications of a Data Structure for Finding Pairwise Interactions. Discrete & Computational Geometry, 22(4):569-592, 1999. URL: https://doi.org/10.1145/276884.276891.
- Martin Held and Peter Palfrader. Straight Skeletons with Additive and Multiplicative Weights and Their Application to the Algorithmic Generation of Roofs and Terrains. Computer-Aided Design, 92(1):33-41, 2017. URL: https://doi.org/10.1016/j.cad.2017.07.003.
- Peter Palfrader, Martin Held, and Stefan Huber. On Computing Straight Skeletons by Means of Kinetic Triangulations. In Proceedings of the 20th Annual European Symposium on Algorithms (ESA), pages 766-777, 2012. URL: https://doi.org/10.1007/978-3-642-33090-2_66.