Publications

2017

Planar Matchings for Weighted Straight Skeletons
Therese Biedl, Stefan Huber, and Peter Palfrader
International Journal of Computational Geometry & Applications, 26(3 & 4):221–229, September & December 2016.
published April 2017
We introduce planar matchings on directed pseudo-line arrangements, which yield a planar set of pseudo-line segments such that only matching-partners are adjacent. By translating the planar matching problem into a corresponding stable roommates problem we show that such matchings always exist. Using our new framework, we establish, for the first time, a complete, rigorous definition of weighted straight skeletons, which are based on a so-called wavefront propagation process. We present a generalized and unified approach to treat structural changes in the wavefront that focuses on the restoration of weak planarity by finding planar matchings.
@article{BieHP16a, author = {Therese Biedl and Stefan Huber and Peter Palfrader}, title = {{P}lanar {M}atchings for {W}eighted {S}traight {S}keletons}, journal = {International Journal of Computational Geometry \& Applications}, year = {2016}, volume = {26}, number = {3 \& 4}, pages = {221--229}, month = {September \& December}, note = {published April 2017}, doi = {10.1142/S0218195916600050}, }
Straight Skeletons of Monotone Surfaces in Three-Space
Martin Held and Peter Palfrader
In Proceedings of the 33nd European Workshop on Computational Geometry (EuroCG 2017), Malmö, Sweden, April 2017
We present a simple algorithm to compute the straight skeleton and mitered offset surfaces of a polyhedral terrain in 3D. Like its 2D pedant, the 3D straight skeleton is the result of a wavefront propagation process, which we simulate in order to construct the skeleton in time \mathcal{O}(n^4 \log n), where n is the number of vertices of the terrain. Any mitered offset surface can then be obtained from the skeleton in time linear in the combinatorial size of the skeleton.
@inproceedings{HePa17a, author = {Martin Held and Peter Palfrader}, title = {{S}traight {S}keletons of {M}onotone {S}urfaces in {T}hree-{S}pace}, booktitle = {Proceedings of the 33nd European Workshop on Computational Geometry (EuroCG 2017)}, year = {2017}, address = {Malmö, Sweden}, month = {April}, }

2016

Weighted Skeletal Structures in Theory and Practice
Peter Palfrader
PhD thesis, University of Salzburg, Salzburg, Austria, April 2016
This cumulative thesis comprises work previously published or still under review for publication, namely PaHe15, HelHP16a, Bie&15a, BieHP14b, a full paper version of HePa16a, and Bie&15b.
In geometry, a skeletal structure of a polygonal shape attempts to capture the essence of some geometric properties of the original shape. Tasks which are work-intensive or fragile to perform with just the polygonal shape can often be performed efficiently and robustly once an appropriate skeleton has been obtained. For instance, the medial axis of a polygon is such a skeleton, and constant-radius offset curves of a polygon are commonly computed by first constructing the polygon's medial axis.

This thesis presents the author's contribution to the field of computational geometry, in particular with respect to skeletal structures. We cover mitered offsets, which are related to the well-known constant-radius offsets, and variable-radius offsets, where the distance to the input varies even along a single input segment. We study how the former can be obtained from straight skeletons, introduced by Aichholzer et al. two decades ago, and we introduce a suitable skeletal structure that encodes geometric information required to efficiently construct the latter.

Furthermore, this dissertation covers aspects of weighted straight skeletons. We discuss properties of multiplicatively-weighted straight skeletons in detail for different classes of input. We establish that, even in the presence of negative weights, they are always well-defined since events of the underlying wavefront propagation can be handled in all cases. We introduce additively-weighted straight skeletons, discuss their properties, and show how skeletons with both additive and multiplicative weights can be used in roof and terrain modeling.

Additionally, we present an algorithm to compute the positively-weighted straight skeleton for monotone polygons with n vertices in \mathcal{O}(n \log n) time.
@phdthesis{Palfrader16, title = {{W}eighted {S}keletal {S}tructures in {T}heory and {P}ractice}, author = {Peter Palfrader}, school = {University of Salzburg}, year = {2016}, address = {Salzburg, Austria}, month = {April}, url = {https://www.palfrader.org/research/k/Palfrader16.pdf}, }
Bisector Graphs for Min-/Max-Volume Roofs over Simple Polygons
Günther Eder, Martin Held, and Peter Palfrader
In Proceedings of the 32nd European Workshop on Computational Geometry (EuroCG 2016), Lugano, Switzerland, March 2016
Piecewise-linear terrains (``roofs'') over simple polygons were studied by Aichholzer et al. (1995) in their work on straight skeletons of polygons. We show how to construct a roof over a simple polygon that has minimum (or maximum) volume among all roofs that drain water. Such a maximum-volume (minimum-volume) roof can have quadratic (maybe cubic, resp.) number of facets. Our algorithm for computing such a roof extends the standard wavefront propagation known from the theory of straight skeletons by two additional events. Both the minimum-volume and the maximum-volume roof of a simple polygon with n vertices can be computed in \mathcal{O}(n^3 \log n) time.
@inproceedings{EdeHP16a, title = {{B}isector {G}raphs for {M}in-/{M}ax-{V}olume {R}oofs over {S}imple {P}olygons}, author = {Günther Eder and Martin Held and Peter Palfrader}, booktitle = {Proceedings of the 32nd European Workshop on Computational Geometry (EuroCG 2016)}, year = {2016}, address = {Lugano, Switzerland}, month = {March}, }
Additive Weights for Straight Skeletons
Martin Held and Peter Palfrader
In Proceedings of the 32nd European Workshop on Computational Geometry (EuroCG 2016), Lugano, Switzerland, March 2016
We introduce an additively-weighted straight skeleton as a new generalization of straight skeletons. It is induced by a wavefront propagation process where, unlike in standard variants, wavefront edges do not necessarily start to move at the begin of the propagation process but at later points in time.
@inproceedings{HePa16a, title = {{A}dditive {W}eights for {S}traight {S}keletons}, author = {Martin Held and Peter Palfrader}, booktitle = {Proceedings of the 32nd European Workshop on Computational Geometry (EuroCG 2016)}, year = {2016}, address = {Lugano, Switzerland}, month = {March}, }
Generalized Offsetting of Planar Structures Using Skeletons
Martin Held, Stefan Huber, and Peter Palfrader
Computer-Aided Design and Applications, 13(5):712–721, 2016
We study different means to extend offsetting based on skeletal structures beyond the well-known constant-radius and mitered offsets supported by Voronoi diagrams and straight skeletons, for which the orthogonal distance of offset elements to their respective input elements is constant and uniform over all input elements. Our main contribution is a new geometric structure, called variable-radius Voronoi diagram, which supports the computation of variable-radius offsets, i.e., offsets whose distance to the input is allowed to vary along the input. We discuss properties of this structure and sketch a prototype implementation that supports the computation of variable-radius offsets based on this new variant of Voronoi diagrams.
@article{HelHP16a, title = {{G}eneralized {O}ffsetting of {P}lanar {S}tructures {U}sing {S}keletons}, author = {Martin Held and Stefan Huber and Peter Palfrader}, journal = {Computer-Aided Design and Applications}, year = {2016}, number = {5}, pages = {712--721}, volume = {13}, doi = {10.1080/16864360.2016.1150718}, }

2015

Representing Directed Trees as Straight Skeletons
Oswin Aichholzer, Therese Biedl, Thomas Hackl, Martin Held, Stefan Huber, Peter Palfrader, and Birgit Vogtenhuber
In Proceedings of the 23rd International Symposium on Graph Drawing & Network Visualization (GD 2015), volume 9411 of Lecture Notes in Computer Science, Los Angeles, CA, USA, September 2015. Springer-Verlag
The straight skeleton of a polygon is the geometric graph obtained by tracing the vertices during a mitered offsetting process. It is known that the straight skeleton of a simple polygon is a tree, and one can naturally derive directions on the edges of the tree from the propagation of the shrinking process.

In this paper, we ask the reverse question: Given a tree with directed edges, can it be the straight skeleton of a polygon? And if so, can we find a suitable simple polygon? We answer these questions for all directed trees where the order of edges around each node is fixed.
@inproceedings{Aic&-GD15, title = {{R}epresenting {D}irected {T}rees as {S}traight {S}keletons}, author = {Oswin Aichholzer and Therese Biedl and Thomas Hackl and Martin Held and Stefan Huber and Peter Palfrader and Birgit Vogtenhuber}, booktitle = {Proceedings of the 23rd International Symposium on Graph Drawing \& Network Visualization (GD 2015)}, year = {2015}, address = {Los Angeles, CA, USA}, month = {September}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, volume = {9411}, doi = {10.1007/978-3-319-27261-0_28}, eprint = {1508.01076}, eprinttype = {arxiv}, }
Experiments on Parallel Polygon Triangulation Using Ear Clipping
Günther Eder, Martin Held, and Peter Palfrader
In Proceedings of the 4th Computational Geometry Week: Young Reseachers Forum (CG-YRF 2015), pages 18–19, Eindhoven, Netherlands, June 2015
We present an experimental study of different strategies for triangulating polygons in parallel. As usual, we call three consecutive vertices of a polygon an ear if the triangle that is spanned by them is completely inside the polygon. Extensive tests on thousands of sample polygons indicate that about 50 percent of the vertices of most polygons form ears, which suggests that polygon-triangulation algorithms based on ear-clipping might be well-suited for parallelization.

We discuss three different on-core approaches to parallelizing ear clipping and report on our experimental findings. Extensive tests show that the most promising method achieves an average speedup of about 3 on a quad-core processor.
@inproceedings{EdeHP15b, title = {{E}xperiments on {P}arallel {P}olygon {T}riangulation {U}sing {E}ar {C}lipping}, author = {Günther Eder and Martin Held and Peter Palfrader}, booktitle = {Proceedings of the 4th Computational Geometry Week: Young Reseachers Forum (CG-YRF 2015)}, year = {2015}, address = {Eindhoven, Netherlands}, month = {June}, pages = {18--19}, }
Variable Offsetting of Polygonal Structures Using Skeletons
Martin Held, Stefan Huber, and Peter Palfrader
In Proceedings of the 12th Computer-Aided Design Conference (CAD 2015), pages 264–268, London, United Kingdom, June 2015.
An extended version is to appear in CADA
@inproceedings{HelHP15a, title = {{V}ariable {O}ffsetting of {P}olygonal {S}tructures {U}sing {S}keletons}, author = {Martin Held and Stefan Huber and Peter Palfrader}, booktitle = {Proceedings of the 12th Computer-Aided Design Conference (CAD 2015)}, year = {2015}, address = {London, United Kingdom}, month = {June}, note = {An extended version is to appear in CADA.}, pages = {264--268}, doi = {10.14733/cadconfP.2015.264-268}, }
Generalized Offsetting Using a Variable-Radius Voronoi Diagram
Martin Held, Stefan Huber, and Peter Palfrader
In Proceedings of the 4th Computational Geometry Week: Young Reseachers Forum (CG-YRF 2015), pages 22–23, Eindhoven, Netherlands, June 2015.
An extended version is to appear in CADA
We investigate ways to extend offsetting based on skeletal structures beyond the well-known constant-radius and mitered offsets supported by Voronoi diagrams and straight skeletons for which the orthogonal distance of offset elements to their input elements is uniform.

We introduce a new geometric structure called the variable-radius Voronoi diagram, which supports the computation of variable-radius offsets, i.e., offsets whose distance to the input may vary along the input.
@inproceedings{HelHP15b, title = {{G}eneralized {O}ffsetting {U}sing a {V}ariable-{R}adius {V}oronoi {D}iagram}, author = {Martin Held and Stefan Huber and Peter Palfrader}, booktitle = {Proceedings of the 4th Computational Geometry Week: Young Reseachers Forum (CG-YRF 2015)}, year = {2015}, address = {Eindhoven, Netherlands}, month = {June}, note = {An extended version is to appear in CADA.}, pages = {22--23}, }
Experiments on Parallel Polygon Triangulation Using Ear Clipping
Günther Eder, Martin Held, and Peter Palfrader
In Proceedings of the 31st European Workshop on Computational Geometry (EuroCG 2015), pages 220–223, Ljubljana, Slovenia, March 2015
We present an experimental study of different strategies for triangulating polygons in parallel. As usual, we call three consecutive vertices of a polygon an ear if the triangle that is spanned by them is completely inside of the polygon. Extensive tests on thousands of sample polygons indicate that most polygons have a linear number of ears. This experimental result suggests that polygon-triangulation algorithms based on ear clipping might be well-suited for parallelization.

We discuss three different on-core approaches to parallelizing ear clipping and report on our experimental findings. Extensive tests show that the most promising method achieves a speedup by a factor of roughly k on a machine with k cores.
@inproceedings{EdeHP15a, title = {{E}xperiments on {P}arallel {P}olygon {T}riangulation {U}sing {E}ar {C}lipping}, author = {Günther Eder and Martin Held and Peter Palfrader}, booktitle = {Proceedings of the 31st European Workshop on Computational Geometry (EuroCG 2015)}, year = {2015}, address = {Ljubljana, Slovenia}, month = {March}, pages = {220--223}, }
Weighted Straight Skeletons in the Plane
Therese Biedl, Martin Held, Stefan Huber, Dominik Kaaser, and Peter Palfrader
Computational Geometry: Theory and Applications, 48(2):120–133, February 2015
We investigate weighted straight skeletons from a geometric, graph-theoretical, and combinatorial point of view. We start with a thorough definition and shed light on some ambiguity issues in the procedural definition. We investigate the geometry, combinatorics, and topology of faces and the roof model, and we discuss in which cases a weighted straight skeleton is connected. Finally, we show that the weighted straight skeleton of even a simple polygon may be non-planar and may contain cycles, and we discuss under which restrictions on the weights and/or the input polygon the weighted straight skeleton still behaves similar to its unweighted counterpart. In particular, we obtain a non-procedural description and a linear-time construction algorithm for the straight skeleton of strictly convex polygons with arbitrary weights.
@article{Bie&15a, title = {{W}eighted {S}traight {S}keletons in the {P}lane}, author = {Therese Biedl and Martin Held and Stefan Huber and Dominik Kaaser and Peter Palfrader}, journal = {Computational Geometry: Theory and Applications}, year = {2015}, month = {February}, number = {2}, pages = {120--133}, volume = {48}, comment = {reprinted in CGTA, 2015, 48, (5), 429--442; doi:10.1016/j.comgeo.2015.01.004}, doi = {10.1016/j.comgeo.2014.08.006}, }
A Simple Algorithm for Computing Positively Weighted Straight Skeletons of Monotone Polygons
Therese Biedl, Martin Held, Stefan Huber, Dominik Kaaser, and Peter Palfrader
Information Processing Letters, 115(2):243–247, February 2015
We study the characteristics of straight skeletons of monotone polygonal chains, and use them to devise an algorithm for computing positively weighted straight skeletons of monotone polygons. Our algorithm runs in \mathcal{O}(n \log n) time and \mathcal{O}(n) space, where n denotes the number of vertices of the polygon.
@article{Bie&15b, title = {{A} {S}imple {A}lgorithm for {C}omputing {P}ositively {W}eighted {S}traight {S}keletons of {M}onotone {P}olygons}, author = {Therese Biedl and Martin Held and Stefan Huber and Dominik Kaaser and Peter Palfrader}, journal = {Information Processing Letters}, year = {2015}, month = {February}, number = {2}, pages = {243--247}, volume = {115}, doi = {10.1016/j.ipl.2014.09.021}, }
Computing Mitered Offset Curves Based on Straight Skeletons
Peter Palfrader and Martin Held
Computer-Aided Design and Applications, 12(4):414–424, February 2015
We study the practical computation of mitered and beveled offset curves of planar straight-line graphs (PSLGs), i.e., of arbitrary collections of straight-line segments in the plane that do not intersect except possibly at common end points. The line segments can, but need not, form polygons. Similar to Voronoi-based offsetting, we propose to compute a straight skeleton of the input PSLG as a preprocessing step for mitered offsetting. For this purpose, we extend and adapt Aichholzer and Aurenhammer's triangulation-based straight-skeleton algorithm to make it process real-world data on a conventional finite-precision arithmetic.

We implemented this extended algorithm in C and use our implementation for extensive experiments. All tests demonstrate the practical suitability of using straight skeletons for the offsetting of complex PSLGs. Our main practical contribution is strong experimental evidence that mitered offsets of PSLGs with 100 000 segments can be computed in about ten milliseconds on a standard PC once the straight skeleton is available and that our implementation clearly is the fastest code for mitered offsetting even if the computational costs of the straight-skeleton computation are included in the timings.
@article{PaHe15, title = {{C}omputing {M}itered {O}ffset {C}urves {B}ased on {S}traight {S}keletons}, author = {Peter Palfrader and Martin Held}, journal = {Computer-Aided Design and Applications}, year = {2015}, month = {February}, number = {4}, pages = {414--424}, volume = {12}, doi = {10.1080/16864360.2014.997637}, }

2014

Planar Matchings for Weighted Straight Skeletons
Therese Biedl, Stefan Huber, and Peter Palfrader
In Hee-Kap Ahn and Chan-Su Shin, editors, Proceedings of the 25th International Symposium on Algorithms and Computation (ISAAC 2014), volume 8889 of Lecture Notes in Computer Science, pages 117–127, Jeonju, Korea, December 2014. Springer-Verlag
In this paper, we introduce planar matchings on directed pseudo-line arrangements, which yield a planar set of pseudo-line segments such that only matching-partners are adjacent. By translating the planar matching problem into a corresponding stable roommates problem we show that such matchings always exist.

Using our new framework, we establish, for the first time, a complete, rigorous definition of weighted straight skeletons, which are based on a so-called wavefront propagation process. We present a generalized and unified approach to treat structural changes in the wavefront that focuses on the restoration of weak planarity by finding planar matchings.
@inproceedings{BieHP14b, title = {{P}lanar {M}atchings for {W}eighted {S}traight {S}keletons}, author = {Therese Biedl and Stefan Huber and Peter Palfrader}, booktitle = {Proceedings of the 25th International Symposium on Algorithms and Computation (ISAAC 2014)}, year = {2014}, address = {Jeonju, Korea}, editor = {Hee-Kap Ahn and Chan-Su Shin}, month = {December}, pages = {117--127}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, volume = {8889}, doi = {10.1007/978-3-319-13075-0_10}, }
Computing Mitered Offset Curves Based on Straight Skeletons
Peter Palfrader and Martin Held
In Proceedings of the 11th Computer-Aided Design Conference (CAD 2014), pages 97–99, Hong Kong, China, June 2014.
Best Paper Award; An extended version appeared in CADA 12(4):414–424, Feb 2015 [PaHe15]
@inproceedings{PaHe14, title = {{C}omputing {M}itered {O}ffset {C}urves {B}ased on {S}traight {S}keletons}, author = {Peter Palfrader and Martin Held}, booktitle = {Proceedings of the 11th Computer-Aided Design Conference (CAD 2014)}, year = {2014}, address = {Hong Kong, China}, month = {June}, note = {Best Paper Award; An extended version appeared in CADA 12(4):414–424, Feb 2015 [PaHe15].}, pages = {97--99}, doi = {10.14733/cadconfP.2014.97-99}, }
Straight Skeletons of Monotone Polygons
Therese Biedl, Martin Held, Stefan Huber, Dominik Kaaser, and Peter Palfrader
In Proceedings of the 30th European Workshop on Computational Geometry (EuroCG 2014), Ein-Gedi, Israel, March 2014.
An extended version appeared in IPL 15(2):243–247, Feb 2015 [Bie&15b]
We study the characteristics of straight skeletons of strictly monotone polygonal chains, and use them to devise an algorithm for computing positively weighted straight skeletons of strictly monotone polygons. Our algorithm runs in \mathcal{O}(n \log n) time and \mathcal{O}(n) space.
@inproceedings{Bie&14, title = {{S}traight {S}keletons of {M}onotone {P}olygons}, author = {Therese Biedl and Martin Held and Stefan Huber and Dominik Kaaser and Peter Palfrader}, booktitle = {Proceedings of the 30th European Workshop on Computational Geometry (EuroCG 2014)}, year = {2014}, address = {Ein-Gedi, Israel}, month = {March}, note = {An extended version appeared in IPL 15(2):243–247, Feb 2015 [Bie\&15b].}, }
Stable Roommates for Weighted Straight Skeletons
Therese Biedl, Stefan Huber, and Peter Palfrader
In Proceedings of the 30th European Workshop on Computational Geometry (EuroCG 2014), Ein-Gedi, Israel, March 2014.
An extended version appeared in Proceedings of ISAAC 2014 [BieHP14b]
In this paper, we fill in a gap in the wavefront-based definition of weighted straight skeletons in the presence of multiple simultaneous, co-located split events. We interpret the need to pair up wavefront edges to restore planarity as a particular matching problem. Our results on a stable roommate problem defined on a directed pseudo-line arrangement show that our method always yields a solution. We thereby complete the definition of weighted straight skeletons.
@inproceedings{BieHP14, title = {{S}table {R}oommates for {W}eighted {S}traight {S}keletons}, author = {Therese Biedl and Stefan Huber and Peter Palfrader}, booktitle = {Proceedings of the 30th European Workshop on Computational Geometry (EuroCG 2014)}, year = {2014}, address = {Ein-Gedi, Israel}, month = {March}, note = {An extended version appeared in Proceedings of ISAAC 2014 [BieHP14b].}, }

2013

Computing Straight Skeletons by Means of Kinetic Triangulations
Peter Palfrader
Master's thesis, University of Salzburg, Salzburg, Austria, September 2013
The straight skeleton is a geometric object defined for polygons, or, more generally, planar straight-line graphs (PSLGs). It was introduced to computational geometry in 1995 by Aichholzer, Aurenhammer, Alberts, and Gärtner. Roughly, a straight skeleton is a planar straight-line graph motivated by a particular shrinking process of a polygon. It introduces a partition similar to that of a Voronoi diagram.

We extensively study Aichholzer and Aurenhammer's 1998 kinetic triangulation-based algorithm to construct the straight skeleton for PSLGs. In particular, we establish that their algorithm is not properly defined for input that is not in general position. We introduce our extensions which are required so that the algorithm works correctly and terminates for all input — even when using only finite-precision arithmetic.

We also present our implementation of the refined algorithm, Surfer, and report on our extensive experiments. We provide strong experimental evidence that the number of flip events is linear in practice; the theoretical bound is in \mathcal{O}(n^3). Our measurements further establish that for practical input the algorithm runs in approximately \mathcal{O}(n \log n) time and that our implementation is clearly the fastest straight-skeleton code currently in existence, improving on Huber's implementation by a factor of 10 and on CGAL's by at least a factor linear in the input size.

This thesis builds on and extends work already presented at ESA2012, the 20th Annual European Symposium on Algorithms in Ljubljana, Slovenia (Palfrader, Held, Huber — On Computing Straight Skeletons by Means of Kinetic Triangulations).
@mastersthesis{Palfrader13, title = {{C}omputing {S}traight {S}keletons by {M}eans of {K}inetic {T}riangulations}, author = {Peter Palfrader}, school = {University of Salzburg}, year = {2013}, address = {Salzburg, Austria}, month = {September}, url = {https://www.palfrader.org/research/2013/master-thesis.pdf}, }
Weighted Straight Skeletons in the Plane
Therese Biedl, Martin Held, Stefan Huber, Dominik Kaaser, and Peter Palfrader
In Proceedings of the 25th Canadian Conference on Computational Geometry (CCCG 2013), pages 13–18, Waterloo, ON, Canada, August 2013.
An extended version appeared in CGTA 48(2):120–133, Feb 2015 [Bie&15a]
In this paper, we investigate the weighted straight skeleton from a geometric, graph-theoretical and combinatorial point of view. We start with a thorough definition, shed light on an ambiguity issue in the procedural definition, and propose solutions. We investigate the geometry of faces and the roof model and we discuss in which cases the straight skeleton is connected. Finally, we show that the weighted straight skeleton of even a simple polygon may be non-planar and may contain cycles, and we discuss under which circumstances the weighted straight skeleton still behaves similar to its unweighted pendant.
@inproceedings{Bie&13, title = {{W}eighted {S}traight {S}keletons in the {P}lane}, author = {Therese Biedl and Martin Held and Stefan Huber and Dominik Kaaser and Peter Palfrader}, booktitle = {Proceedings of the 25th Canadian Conference on Computational Geometry (CCCG 2013)}, year = {2013}, address = {Waterloo, ON, Canada}, month = {August}, note = {An extended version appeared in CGTA 48(2):120–133, Feb 2015 [Bie\&15a].}, pages = {13--18}, }

2012

On Computing Straight Skeletons by Means of Kinetic Triangulations
Peter Palfrader, Martin Held, and Stefan Huber
In Leah Epstein and Paolo Ferragina, editors, Proceedings of the 20th Annual European Symposium on Algorithms (ESA 2012), volume 7501 of Lecture Notes in Computer Science, pages 766–777, Ljubljana, Slovenia, September 2012. Springer-Verlag
We study the computation of the straight skeleton of a planar straight-line graph (PSLG) by means of the triangulation-based wavefront propagation proposed by Aichholzer and Aurenhammer in 1998, and provide both theoretical and practical insights. As our main theoretical contribution we explain the algorithmic extensions and modifications of their algorithm necessary for computing the straight skeleton of a general PSLG within the entire plane, without relying on an implicit assumption of general position of the input, and when using a finite-precision arithmetic. We implemented this extended algorithm in C and report on extensive experiments. Our main practical contribution is (1) strong experimental evidence that the number of flip events that occur in the kinetic triangulation of real-world data is linear in the number n of input vertices, (2) that our implementation, Surfer, runs in \mathcal{O}(n \log n) time on average, and (3) that it clearly is the fastest straight-skeleton code currently available.
@inproceedings{PalHH12, title = {{O}n {C}omputing {S}traight {S}keletons by {M}eans of {K}inetic {T}riangulations}, author = {Peter Palfrader and Martin Held and Stefan Huber}, booktitle = {Proceedings of the 20th Annual European Symposium on Algorithms (ESA 2012)}, year = {2012}, address = {Ljubljana, Slovenia}, editor = {Leah Epstein and Paolo Ferragina}, month = {September}, pages = {766--777}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, volume = {7501}, doi = {10.1007/978-3-642-33090-2_66}, }

Other stuff

Things I did as an undergrad and grad student: