Weighted and Unweighted Straight Skeletons

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.

In joint work with Stefan Huber, Willi Mann and Peter Palfrader, we investigated the use of kinetic triangulations for computing motorcycle graphs and straight skeletons. The use of kinetic triangulations for computing straight skeletons had been advocated by Aichholzer and Aurenhammer (1998), but it turned out that we had to fill serious algorithmic gaps in order to be able to implement this approach. Its main advantage seems to be that the cpu-time consumption of this approach is less sensitive to irregularities of the input data, such as a non-uniform distribution of the motorcycles. And it runs significantly better in practice than predicted by its theoretical worst-case complexity!

This research was supported by the Austrian FWF Grant P 25816-N15.

Sample Straight Skeletons and Mitered Offsets:

The subsequent images were computed by Peter Palfrader's SURFER, our straight-skeleton algorithm that makes use of kinetic triangulations. Click on the thumbnails in order to see larger images.

				A tribute to SURFER's designer.
				Straight skeleton and a family of mitered offsets within a simplified outline of Austria.
				Straight skeleton of a multiply-connected area defined by linearized circles.
				Straight skeleton of a PSLG.
				Straight skeleton and a family of mitered offsets of a horse-shaped polygon.
				Standard straight skeleton and mitered offsets (left) versus a linear axis and offsets with multi-segment bevels (right).
				Straight skeleton of a polygon whose edges are parallel to a coordinate axis or a main diagonal.
				Straight skeleton of a fairly smooth shape.

Related publications:

G. Eder, M. Held (2018):
"Computing Positively Weighted Straight Skeletons of Simple Polygons Based on a Bisector Arrangement".
Information Processing Letters, 132:28-32, Apr 2018.

T. Biedl, S. Huber, P. Palfrader (2016):
"Planar Matchings for Weighted Straight Skeletons".
Int. Journal of Computational Geometry & Applications, 26(3&4):221-229, Dec 2016. Published Apr 2017.

P. Palfrader, M. Held (2015):
"Computing Mitered Offset Curves Based on Straight Skeletons".
Computer-Aided Design and Applications, 12(4):414-424, 2015.

T. Biedl, M. Held, S. Huber, D. Kaaser, P. Palfrader (2015):
"A Simple Algorithm for Computing Positively Weighted Straight Skeletons of Monotone Polygons".
Information Processing Letters, 115(2):243-247, Feb 2015.

T. Biedl, M. Held, S. Huber, D. Kaaser, P. Palfrader (2015):
"Weighted Straight Skeletons in the Plane".
Computational Geometry: Theory and Applications, 48(2):120-133, Feb 2015.

P. Palfrader, M. Held (2014):
"Computing Mitered Offset Curves Based on Straight Skeletons".
Proc. 11th Annual CAD Conference, p. 97-99, Hong Kong, China, June 2014.

T. Biedl, M. Held, S. Huber, D. Kaaser, P. Palfrader (2014):
"Straight Skeletons of Monotone Polygons".
Proc. 30th Europ. Workshop Computational Geometry, Ein-Gedi, Isreal, March 2014.

T. Biedl, M. Held, S. Huber, D. Kaaser, P. Palfrader (2013):
"Weighted Straight Skeletons in the Plane".
Proc. 25th Canadian Conf. on Computational Geometry, p. 13-18, Waterloo, ON, Canada, Aug 2013.

T. Biedl, M. Held, S. Huber (2013):
"Recognizing Straight Skeletons and Voronoi Diagrams and Reconstructing Their Input".
Proc. 10th Int. Symp. on Voronoi Diagrams in Science and Engineering, p. 37-46, St. Petersburg, Russia, July 2013.

P. Palfrader, M. Held, S. Huber (2012):
"On Computing Straight Skeletons by Means of Kinetic Triangulations".
Proc. 20th Annu. Europ. Symp. Algorithms, Ljubljana, Slovenia, p. 766-777, Sep 2012.

W. Mann, M. Held, S. Huber (2012):
"Computing Motorcycle Graphs Based on Kinetic Triangulations".
Proc. 24th Canadian Conf. on Computational Geometry, p. 187-192, Charlottetown, P.E.I., Canada, Aug 2012.

file last modified: Thursday, 27-Feb-2020 07:29:08 CET