Weighted Straight Skeletons and Exact Arithmetic

Aichholzer et al. (1995) introduced the straight skeleton of a simple polygon as a skeleton structure similar to Voronoi diagrams. Roughly speaking, the straight skeleton of a simple polygon is defined by a wavefront propagation process where the edges move inwards in a self-parallel manner. The traces of the moving vertices of this process form the straight skeleton.

Recently we worked on 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: Monos on GitHub and Surfer2 on GitHub.

This research was supported by the Austrian FWF Grant ORD 53. Joint work with Günther Eder and Peter Palfrader.

Related publications:

G. Eder, M. Held, P. Palfrader (2020):
"On Implementing Straight Skeletons: Challenges and Experiences".
Proc. 36th Symp. on Computational Geometry, 38:1--38:16, Zürich, Switzerland, June 2020.

G. Eder, M. Held, P. Palfrader (2020):
"Step-by-Step Straight Skeletons".
Proc. 36th Symp. on Computational Geometry CG:ME, 76:1-76:4, Zürich, Switzerland, June 2020.

G. Eder, M. Held, P. Palfrader (2020):
"Experimental Evaluation of Straight Skeleton Implementations Based on Exact Arithmetic".
Proc. 36th EuroCG, pp. 40:1-40:8, Würzburg, Germany, March 2020.

Video presentation of Surfer2 and Monos by Peter Palfrader (2020).

file last modified: Tuesday, 09-Jun-2020 12:31:26 CEST
held@cs.sbg.ac.at