# Publications

## 2022

2-Opt Moves and Flips for Area-Optimal Polygonalizations

*ACM Journal of Experimental Algorithmics*, 27, December 2022

- abstract
- BibTeX
- artice (PDF)
- 10.1145/3500913

Our work on the Computational Geometry Challenge 2019 on area-optimal polygonizations is based on two key components: (1) sampling the search space to obtain initial polygonizations and (2) optimizing such a polygonizations. Among other heuristics for obtaining polygonizations for a given set P of input points, we discuss how to combine 2-opt moves with a line sweep to convert an initial random (non-simple) polygon whose vertices are given by P into a polygonization P. The actual optimization relies on a constrained triangulation of the interior and exterior of a polygonization to speed-up local modifications of the polygonization to increase or decrease its area.

@article{Ede&22a,
author = {Günther Eder and Martin Held and Steinþór Jasonarson and Philipp Mayer and Peter Palfrader},
title = {{2-Opt} {M}oves and {F}lips for {A}rea-{O}ptimal {P}olygonalizations},
journal = {ACM Journal of Experimental Algorithmics},
year = {2022},
volume = {27},
month = {December},
doi = {10.1145/3500913},
}

Modeling Coverage Areas of Anisotropic Transmitters by Voronoi-like
Structures

*Computer-Aided Design and Applications*, 19(5):967–976, 2022

- abstract
- BibTeX
- artice (PDF)
- 10.14733/cadaps.2022.967-976

The geometric modeling of coverage areas is a well-known problem in the analysis of networks of sensor or transmitters. Prior work often uses Voronoi diagrams of the device locations to obtain estimates of their coverage areas in the plane. In this work we extend these approaches by allowing the signal propagation to be non-uniform both among the devices as well as relative to different directions for an individual device. Depending on whether or not the spreading of an anisotropic signal is stopped once it reaches a point of the plane that has already been covered by some other signal, we get connected or disconnected coverage areas. A proof-of-concept implementation of our algorithms is freely available via GitHub.

@article{HePa22a,
author = {Martin Held and Peter Palfrader},
title = {{Modeling Coverage Areas of Anisotropic Transmitters by Voronoi-like Structures}},
journal = {Computer-Aided Design and Applications},
year = {2022},
volume = {19},
number = {5},
pages = {967--976},
doi = {10.14733/cadaps.2022.967-976},
}

## 2021

Modeling Coverage Areas of Anisotropic Transmitters by Voronoi-like
Structures

In

*Proceedings of the 18th Computer-Aided Design Conference (CAD 2021)*, pages 283–287, Barcelona, Spain, July 2021@inproceedings{HePa21a,
author = {Martin Held and Peter Palfrader},
title = {{Modeling Coverage Areas of Anisotropic Transmitters by Voronoi-like Structures}},
booktitle = {Proceedings of the 18th Computer-Aided Design Conference (CAD 2021)},
year = {2021},
pages = {283--287},
address = {Barcelona, Spain},
month = {July},
doi = {10.14733/cadconfP.2021.283-287},
}

Implementing Straight Skeletons with Exact Arithmetic:
Challenges and Experiences

*Computational Geometry: Theory and Applications*, 96, June 2021

- abstract
- BibTeX
- article (PDF)
- 10.1016/j.comgeo.2021.101760

We present 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. We discuss algorithmic as well as implementational and engineering details of both codes. Furthermore, we present the results of an extensive performance evaluation in which we compared Surfer2 and Monos to the straight-skeleton package included in Cgal. It is not surprising that our special-purpose code Monos outperforms Cgal's straight-skeleton implementation. But our tests provide ample evidence that also Surfer2 can be expected to be faster and to consume significantly less memory than the Cgal code. And, of course, Surfer2 is more versatile because it can handle multiplicative weights and general PSLGs as input. Thus, Surfer2 currently is the fastest and most general straight-skeleton code available.

@article{Ede&21,
author = {Günther Eder and Martin Held and Peter Palfrader},
title = {{I}mplementing {S}traight {S}keletons with {E}xact {A}rithmetic: {C}hallenges and {E}xperiences},
journal = {Computational Geometry: Theory and Applications},
year = {2021},
volume = {96},
month = {June},
issn = {0925-7721},
doi = {10.1016/j.comgeo.2021.101760},
}

## 2020

Salzburg Database of Polygonal Data: Polygons and Their
Generators

*Data in Brief*, 31:105984, August 2020

- abstract
- BibTeX
- article (PDF)
- The Salzburg Database
- 10.1016/j.dib.2020.105984

The Salzburg Database is a repository of polygonal areas of various classes and sizes, with and without holes. Positive weights are assigned to all edges of all polygons. We introduce this collection and describe the generators that produced its polygons. The source codes for all generators as well as the polygons generated are publicly available.

@article{Ede&20d,
author = {Eder, Günther and Held, Martin and Jasonarson, Steinþór and Mayer, Philipp and Palfrader, Peter},
title = {{S}alzburg {D}atabase of {P}olygonal {D}ata: {P}olygons and {T}heir {G}enerators},
journal = {Data in Brief},
year = {2020},
volume = {31},
pages = {105984},
month = {August},
issn = {2352-3409},
doi = {10.1016/j.dib.2020.105984},
}

Computing Low-Cost Convex Partitions for Planar Point
Sets Based on Tailored Decompositions

In Sergio Cabello and Danny Z. Chen, editors,

*36th International Symposium on Computational Geometry (SoCG 2020)*, volume 164 of*LIPIcs*, pages 85:1–85:10, Zürich, Switzerland, June 2020. Schloss Dagstuhl–Leibniz-Zentrum für Informatik- abstract
- BibTeX
- paper (PDF)
- SoCG/CGWeek 2020
- 10.4230/LIPIcs.SoCG.2020.85

Our work on minimum convex decompositions is based on two key components: (1) different strategies for computing initial decompositions, partly adapted to the characteristics of the input data, and (2) local optimizations for reducing the number of convex faces of a decomposition. We discuss our main heuristics and show how they helped to reduce the face count.

@inproceedings{Ede&20c,
author = {Günther Eder and Martin Held and Stefan de Lorenzo and Peter Palfrader},
title = {{C}omputing {L}ow-{C}ost {C}onvex {P}artitions for {P}lanar {P}oint {S}ets {B}ased on {T}ailored {D}ecompositions},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
year = {2020},
editor = {Sergio Cabello and Danny Z. Chen},
volume = {164},
series = {LIPIcs},
pages = {85:1--85:10},
address = {Zürich, Switzerland},
month = {June},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum für Informatik},
doi = {10.4230/LIPIcs.SoCG.2020.85},
isbn = {978-3-95977-143-6},
issn = {1868-8969},
urn = {urn:nbn:de:0030-drops-122438},
}

On Implementing Straight Skeletons: Challenges and
Experiences

In Sergio Cabello and Danny Z. Chen, editors,

*36th International Symposium on Computational Geometry (SoCG 2020)*, volume 164 of*LIPIcs*, pages 38:1–38:16, Zürich, Switzerland, June 2020. Schloss Dagstuhl–Leibniz-Zentrum für Informatik- abstract
- BibTeX
- paper (PDF)
- SoCG/CGWeek 2020
- 10.4230/LIPIcs.SoCG.2020.38

We present C++ 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. We discuss algorithmic as well as implementational and engineering details of both codes. Furthermore, we present the results of an extensive performance evaluation in which we compared Surfer2 and Monos to the straight-skeleton package included in CGAL. It is not surprising that our special-purpose code Monos outperforms CGAL's straight-skeleton implementation. But our tests provide ample evidence that also Surfer2 can be expected to be faster and to consume significantly less memory than the CGAL code. And, of course, Surfer2 is more versatile because it can handle multiplicative weights and general PSLGs as input. Thus, Surfer2 currently is the fastest and most general straight-skeleton code available.

@inproceedings{EdeHP20a,
author = {Günther Eder and Martin Held and Peter Palfrader},
title = {{O}n {I}mplementing {S}traight {S}keletons: {C}hallenges and {E}xperiences},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
year = {2020},
editor = {Sergio Cabello and Danny Z. Chen},
volume = {164},
series = {LIPIcs},
pages = {38:1--38:16},
address = {Zürich, Switzerland},
month = {June},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum für Informatik},
doi = {10.4230/LIPIcs.SoCG.2020.38},
isbn = {978-3-95977-143-6},
issn = {1868-8969},
urn = {urn:nbn:de:0030-drops-121964},
}

Step-By-Step Straight Skeletons

In Sergio Cabello and Danny Z. Chen, editors,

*36th International Symposium on Computational Geometry (SoCG 2020)*, volume 164 of*LIPIcs*, pages 76:1–76:4, Zürich, Switzerland, June 2020. Schloss Dagstuhl–Leibniz-Zentrum für Informatik- abstract
- BibTeX
- paper (PDF)
- SoCG/CGWeek 2020
- Videos: monos, surfer2
- Source Code: monos, surfer2
- 10.4230/LIPIcs.SoCG.2020.76

We present two software packages for computating straight skeletons: Monos, our implementation of an algorithm by Biedl et al. (2015), computes the straight skeleton of a monotone input polygon, and Surfer2 implements a generalization of an algorithm by Aichholzer and Aurenhammer (1998) to handle multiplicatively-weighted planar straight-line graphs as input. The graphical user interfaces that ship with our codes support step-by-step computations, where each event can be investigated and studied by the user. This makes them a canonical candidate for educational purposes and detailed event analyses. Both codes are freely available on GitHub.

@inproceedings{EdeHP20c,
author = {Günther Eder and Martin Held and Peter Palfrader},
title = {{S}tep-{B}y-{S}tep {S}traight {S}keletons},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
year = {2020},
editor = {Sergio Cabello and Danny Z. Chen},
volume = {164},
series = {LIPIcs},
pages = {76:1--76:4},
address = {Zürich, Switzerland},
month = {June},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum für Informatik},
doi = {10.4230/LIPIcs.SoCG.2020.76},
isbn = {978-3-95977-143-6},
issn = {1868-8969},
urn = {urn:nbn:de:0030-drops-122343},
}

On Generating Polygons: Introducing the Salzburg
Database

In

*Proceedings of the 36th European Workshop on Computational Geometry (EuroCG 2020)*, pages 75:1–75:7, Würzburg, Germany, March 2020- abstract
- BibTeX
- paper (PDF)
- presentation slides (Günther Eder)
- presentation video (Günther Eder)
- presentation video on YT
- EuroCG 2020
- The Salzburg Database

The Salzburg Database is a repository of polygonal areas of various classes and sizes, with and without holes. Positive weights are assigned to all edges of all polygons. We introduce this collection and briefly describe the generators that produced its polygons. The source codes for all generators as well as the polygons generated are publicly available.

@inproceedings{Ede&20a,
author = {Günther Eder and Martin Held and Steinþór Jasonarson and Philipp Mayer and Peter Palfrader},
title = {{O}n {G}enerating {P}olygons: {I}ntroducing the {S}alzburg {D}atabase},
booktitle = {Proceedings of the 36th European Workshop on Computational Geometry (EuroCG 2020)},
year = {2020},
pages = {75:1--75:7},
address = {Würzburg, Germany},
month = {March},
}

Experimental Evaluation of Straight Skeleton
Implementations Based on Exact Arithmetic

In

*Proceedings of the 36th European Workshop on Computational Geometry (EuroCG 2020)*, pages 40:1–40:8, Würzburg, Germany, March 2020- abstract
- BibTeX
- paper (PDF)
- presentation slides
- presentation video
- presentation video on YT
- EuroCG 2020

We present C++ 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. We sketch implementational and engineering details and discuss the results of an extensive performance evaluation in which we compared Surfer2 and Monos to the straight-skeleton package included in CGAL. Our tests provide ample evidence that both implementations can be expected to be faster and to consume significantly less memory than the CGAL code.

@inproceedings{EdeHP20b,
author = {Günther Eder and Martin Held and Peter Palfrader},
title = {{E}xperimental {E}valuation of {S}traight {S}keleton {I}mplementations {B}ased on {E}xact {A}rithmetic},
booktitle = {Proceedings of the 36th European Workshop on Computational Geometry (EuroCG 2020)},
year = {2020},
pages = {40:1--40:8},
address = {Würzburg, Germany},
month = {March},
}

## 2019

Computing the Straight Skeleton of an Orthogonal Monotone
Polygon in Linear Time

In

*Proceedings of the 35th European Workshop on Computational Geometry (EuroCG 2019)*, Utrecht, Netherlands, March 2019- abstract
- BibTeX
- paper (PDF)
- EuroCG 2019

We introduce a simple algorithm to construct the straight skeleton of an -vertex orthogonal monotone polygon in optimal time and space.

@inproceedings{EdeHP19a,
author = {Günther Eder and Martin Held and Peter Palfrader},
title = {{C}omputing the {S}traight {S}keleton of an {O}rthogonal {M}onotone {P}olygon in {L}inear {T}ime},
booktitle = {Proceedings of the 35th European Workshop on Computational Geometry (EuroCG 2019)},
year = {2019},
address = {Utrecht, Netherlands},
month = {March},
}

Min-/Max-Volume Roofs Induced by Bisector Graphs of
Polygonal Footprints of Buildings

*International Journal of Computational Geometry & Applications*, 28(4):309–340, 2019

- abstract
- BibTeX
- article (PDF)
- 10.1142/S0218195918500097

Piecewise-linear terrains (``roofs'') over simple polygons were first studied by Aichholzer et al. (J. UCS 1995) in their work on straight skeletons of polygons. We show how to construct a roof over the polygonal footprint of a building that has minimum or maximum volume among all roofs that drain water. Our algorithm for computing such a roof extends the standard plane-sweep approach known from the theory of straight skeletons by additional events. For both types of roofs our algorithm runs in time for a simple polygon with vertices.

@article{EdeHP19b,
author = {Günther Eder and Martin Held and Peter Palfrader},
title = {{M}in-/{M}ax-{V}olume {R}oofs {I}nduced by {B}isector {G}raphs of {P}olygonal {F}ootprints of {B}uildings},
journal = {International Journal of Computational Geometry \& Applications},
year = {2019},
volume = {28},
number = {4},
pages = {309--340},
doi = {10.1142/S0218195918500097},
}

Recognizing Geometric Trees as Positively Weighted
Straight Skeletons and Reconstructing Their Input

*International Journal of Computational Geometry & Applications*, 29(03):251–267, 2019

- abstract
- BibTeX
- article (PDF)
- 10.1142/S0218195919500080

We extend results by Biedl et al. (ISVD'13) on the recognition and reconstruction of straight skeletons: Given a geometric tree , can we recognize whether resembles a weighted straight skeleton and, if so, can we reconstruct an appropriate polygonal input and an appropriate positive weight function such that ? We show that a solution polygon and a weight function can be found in time and space for a geometric tree with faces if at most one node of has two incident edges that span an angle greater than . In addition, we show that implicitly encodes enough information such that all other weighted bisectors of any solution can be obtained from without explicitly computing .

@article{EdeHP19c,
author = {Günther Eder and Martin Held and Peter Palfrader},
title = {{R}ecognizing {G}eometric {T}rees as {P}ositively {W}eighted {S}traight {S}keletons and {R}econstructing {T}heir {I}nput},
journal = {International Journal of Computational Geometry \& Applications},
year = {2019},
volume = {29},
number = {03},
pages = {251--267},
doi = {10.1142/S0218195919500080},
}

Straight Skeletons and Mitered Offsets of Polyhedral
Terrains in 3D

*Computer-Aided Design and Applications*, 16(4):611–619, 2019

- abstract
- BibTeX
- artice (PDF)
- 10.14733/cadaps.2019.611-619

We present a simple algorithm to compute the straight skeleton and mitered offset surfaces of a polyhedral terrain in 3D, i.e., of a -monotone piecewise-linear surface. 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 (worst-case) time , where 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.

@article{HePa19a,
author = {Martin Held and Peter Palfrader},
title = {{S}traight {S}keletons and {M}itered {O}ffsets of {P}olyhedral {T}errains in {3D}},
journal = {Computer-Aided Design and Applications},
year = {2019},
volume = {16},
number = {4},
pages = {611--619},
doi = {10.14733/cadaps.2019.611-619},
}

Skeletal Structures for Modeling Generalized Chamfers and
Fillets in the Presence of Complex Miters

*Computer-Aided Design and Applications*, 16(4):620–627, 2019

- abstract
- BibTeX
- artice (PDF)
- 10.14733/cadaps.2019.620-627

A chamfer is a sloped or angled corner or edge that provides a transition between faces of a three-dimensional object. Similarly, a fillet is a rounded corner or edge. We show how to model and construct complex chamfers and fillets for extruded objects in a robust and efficient way even if several faces of the object are involved. Our approach is based on skeletal structures such as the medial axis and straight skeleton of the footprint of the extruded object. It can be seen as a generalization of the standard roofs induced by these structures.

@article{HePa19b,
author = {Martin Held and Peter Palfrader},
title = {{S}keletal {S}tructures for {M}odeling {G}eneralized {C}hamfers and {F}illets in the {P}resence of {C}omplex {M}iters},
journal = {Computer-Aided Design and Applications},
year = {2019},
volume = {16},
number = {4},
pages = {620--627},
doi = {10.14733/cadaps.2019.620-627},
}

## 2018

Parallelized Ear Clipping for the Triangulation and
Constrained Delaunay Triangulation of Polygons

*Computational Geometry: Theory and Applications*, 73:15–23, August 2018

- abstract
- BibTeX
- article (PDF)
- 10.1016/j.comgeo.2018.01.004

We present an experimental study of strategies for triangulating polygons in parallel on multi-core machines, including the parallel computation of constrained Delaunay triangulations. As usual, we call three consecutive vertices of a (planar) 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% of vertices of most polygons form ears. This experimental result suggests that polygon-triangulation algorithms based on ear clipping might be well-suited for parallelization. We discuss three different approaches to parallelizing ear clipping, and we present a parallel edge-flipping algorithm for converting a triangulation into a constrained Delaunay triangulation. All algorithms were implemented as part of Held's FIST framework. We report on our experimental findings, which show that the most promising method achieves an average speedup of – on a quad-core processor. In any case, our new triangulation code is faster than the sequential triangulation codes Triangle (by Shewchuk) and FIST.

@article{EdeHP18a,
author = {Günther Eder and Martin Held and Peter Palfrader},
title = {{P}arallelized {E}ar {C}lipping for the {T}riangulation and {C}onstrained {D}elaunay {T}riangulation of {P}olygons},
journal = {Computational Geometry: Theory and Applications},
year = {2018},
volume = {73},
pages = {15--23},
month = {August},
doi = {10.1016/j.comgeo.2018.01.004},
}

Straight Skeletons and Mitered Offsets of Polyhedral
Terrains in 3D

In

*Proceedings of the 15th Computer-Aided Design Conference (CAD 2018)*, pages 37–41, Paris, France, July 2018@inproceedings{HePa18a,
author = {Martin Held and Peter Palfrader},
title = {{S}traight {S}keletons and {M}itered {O}ffsets of {P}olyhedral {T}errains in {3D}},
booktitle = {Proceedings of the 15th Computer-Aided Design Conference (CAD 2018)},
year = {2018},
pages = {37--41},
address = {Paris, France},
month = {July},
doi = {10.14733/cadconfP.2018.37-41},
}

Skeletal Structures for Modeling Complex Chamfers and
Fillets

In

*Proceedings of the 15th Computer-Aided Design Conference (CAD 2018)*, pages 42–46, Paris, France, July 2018@inproceedings{HePa18b,
author = {Martin Held and Peter Palfrader},
title = {{S}keletal {S}tructures for {M}odeling {C}omplex {C}hamfers and {F}illets},
booktitle = {Proceedings of the 15th Computer-Aided Design Conference (CAD 2018)},
year = {2018},
pages = {42--46},
address = {Paris, France},
month = {July},
doi = {10.14733/cadconfP.2018.42-46},
}

## 2017

Straight Skeletons with Additive and Multiplicative Weights
and Their Application to the Algorithmic Generation of Roofs and
Terrains

*Computer-Aided Design*, 92:33–41, November 2017

- abstract
- BibTeX
- artice (PDF)
- 10.1016/j.cad.2017.07.003

We introduce additively-weighted straight skeletons as a new generalization of straight skeletons. An additively-weighted straight skeleton is the result of a wavefront-propagation process where, unlike in previous variants of straight skeletons, wavefront edges do not necessarily start to move at the begin of the propagation process but at later points in time. We analyze the properties of additively-weighted straight skeletons and show how to compute straight skeletons with both additive and multiplicative weights.

We then show how to use additively-weighted and multiplicatively-weighted straight skeletons to generate roofs and terrains for polygonal shapes such as the footprints of buildings or river networks. As a result, we get an automated generation of roofs and terrains where the individual facets have different inclinations and may start at different heights.

We then show how to use additively-weighted and multiplicatively-weighted straight skeletons to generate roofs and terrains for polygonal shapes such as the footprints of buildings or river networks. As a result, we get an automated generation of roofs and terrains where the individual facets have different inclinations and may start at different heights.

@article{HePa17b,
author = {Martin Held and Peter Palfrader},
title = {{S}traight {S}keletons with {A}dditive and {M}ultiplicative {W}eights and {T}heir {A}pplication to the {A}lgorithmic {G}eneration of {R}oofs and {T}errains},
journal = {Computer-Aided Design},
year = {2017},
volume = {92},
pages = {33--41},
month = {November},
issn = {0010-4485},
doi = {10.1016/j.cad.2017.07.003},
eprint = {1604.03362},
eprinttype = {arxiv},
}

Planar Matchings for Weighted Straight Skeletons

*International Journal of Computational Geometry & Applications*, 26(3 & 4):221–229, September & December 2016.

published April 2017

- abstract
- BibTeX
- artice (PDF)
- 10.1142/S0218195916600050

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

In

*Proceedings of the 33rd European Workshop on Computational Geometry (EuroCG 2017)*, Malmö, Sweden, April 2017- abstract
- BibTeX
- paper (PDF)
- EuroCG 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 , where 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 33rd European Workshop on Computational Geometry (EuroCG 2017)},
year = {2017},
address = {Malmö, Sweden},
month = {April},
}

## 2016

*Weighted Skeletal Structures in Theory and Practice*

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.

- abstract
- BibTeX
- thesis (abridged, PDF)

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 vertices in time.

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 vertices in 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

In

*Proceedings of the 32nd European Workshop on Computational Geometry (EuroCG 2016)*, Lugano, Switzerland, March 2016- abstract
- BibTeX
- paper (PDF)
- EuroCG 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 vertices can be computed in 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

In

*Proceedings of the 32nd European Workshop on Computational Geometry (EuroCG 2016)*, Lugano, Switzerland, March 2016- abstract
- BibTeX
- paper (PDF)
- EuroCG 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

*Computer-Aided Design and Applications*, 13(5):712–721, 2016

- abstract
- BibTeX
- artice (PDF)
- 10.1080/16864360.2016.1150718

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

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- abstract
- BibTeX
- GD 2015
- preprint: arXiv:1508.01076 [cs.CG]
- PDF (on arXiv)
- The original publication is available at Springer
- 10.1007/978-3-319-27261-0_28

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.

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

In

*Proceedings of the 4th Computational Geometry Week: Young Reseachers Forum (CG-YRF 2015)*, pages 18–19, Eindhoven, Netherlands, June 2015- abstract
- BibTeX
- extended abstract (PDF)
- CGWeek 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.

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

In

An extended version is to appear in CADA

*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

In

An extended version is to appear in CADA

*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

- abstract
- BibTeX
- extended abstract (PDF)
- CGWeek 2015

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

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

In

*Proceedings of the 31st European Workshop on Computational Geometry (EuroCG 2015)*, pages 220–223, Ljubljana, Slovenia, March 2015- abstract
- BibTeX
- paper (PDF)
- EuroCG 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 on a machine with cores.

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 on a machine with 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

*Computational Geometry: Theory and Applications*, 48(2):120–133, February 2015

- abstract
- BibTeX
- article (PDF)
- 10.1016/j.comgeo.2014.08.006

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

*Information Processing Letters*, 115(2):243–247, February 2015

- abstract
- BibTeX
- article (PDF)
- 10.1016/j.ipl.2014.09.021

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 time and space, where 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

*Computer-Aided Design and Applications*, 12(4):414–424, February 2015

- abstract
- BibTeX
- article at Taylor & Francis
- draft (PDF)
- 10.1080/16864360.2014.997637

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.

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

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- abstract
- BibTeX
- paper, draft (PDF)
- The original publication is available at Springer
- ISAAC 2014
- 10.1007/978-3-319-13075-0_10

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.

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

In

Best Paper Award; An extended version appeared in CADA 12(4):414–424, Feb 2015 [PaHe15]

*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]

- BibTeX
- extended abstract, draft (PDF)
- presentation slides (Martin Held)
- CAD Conference 2014
- 10.14733/cadconfP.2014.97-99

@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

In

An extended version appeared in IPL 15(2):243–247, Feb 2015 [Bie&15b]

*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]

- abstract
- BibTeX
- paper (PDF)
- presentation slides
- EuroCG 2014

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 time and 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

In

An extended version appeared in Proceedings of ISAAC 2014 [BieHP14b]

*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]

- abstract
- BibTeX
- paper (PDF)
- presentation slides (Stefan Huber)
- EuroCG 2014

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

Master's thesis, University of Salzburg, Salzburg, Austria, September
2013

- abstract
- BibTeX
- thesis (PDF)
- presentation slides
- errata

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 . Our measurements further establish that for practical input the algorithm runs in approximately 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 —

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 . Our measurements further establish that for practical input the algorithm runs in approximately 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

In

An extended version appeared in CGTA 48(2):120–133, Feb 2015 [Bie&15a]

*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]

- abstract
- BibTeX
- paper (PDF)
- full proceedings
- CCCG 2013

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

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- abstract
- BibTeX
- paper, draft (PDF)
- The original publication is available at Springer
- presentation slides
- ESA 2012
- 10.1007/978-3-642-33090-2_66

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 of input vertices, (2) that our implementation, Surfer, runs in 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:

- A longer version of the Computing Straight Skeletons by Means of Kinetic Triangulations presentation (approximately 45 minutes).
- Randomized Algorithms in Computational Geometry for Martin Held's Algorithm seminar in 2013.
- Presentation on Polygonal Meshes for Martin Held's Geometric Modeling seminar in 2011.
- Presentation for Camera identification from sensor fingerprints: why noise matters together with Yvonne Höller in Andreas Uhl's Multimedia Security class.
- In one of Martin Held's's seminars, my overview on triangulation strips: slides; paper.
- Mini project on the Dining Philosophers for Ana Sokolova's Model Checking class: paper;
- For Christoph Kirsch's Embedded Software Engineering Course, Markus Flatz, Andreas Rottmann, and I built a small robot to solve the Tower of Hanoi problem: paper; slides; video.
- There's a short introduction into Digital Cash [German] which I wrote for Hauptseminar Kryptographische Verfahren.
- A paper I wrote with Wolfgang Klier and Bernhard Stader for Proseminar Einführung in die Bioinformatik: Growing Artificial Neural Networks.