me | department | university | teaching | research | disclaimer | personal stuff



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.

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


Related publications:

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.



[Image of CS Logo]
file last modified: Wednesday, 22-Jun-2016 08:28:55 CEST
email address
Copyright © 2017 Martin Held. All rights reserved.
[Rock climbing]