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.

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.

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: Wednesday, 22-Jun-2016 08:28:55 CEST
Copyright © 2017 Martin Held. All rights reserved. |