Publications

[BibTeX file]

2022

Ede&22a
2-Opt Moves and Flips for Area-Optimal Polygonalizations
Günther Eder, Martin Held, Steinþór Jasonarson, Philipp Mayer, and Peter Palfrader
ACM Journal of Experimental Algorithmics, 27, December 2022
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}, }
HePa22a
Modeling Coverage Areas of Anisotropic Transmitters by Voronoi-like Structures
Martin Held and Peter Palfrader
Computer-Aided Design and Applications, 19(5):967–976, 2022
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

HePa21a
Modeling Coverage Areas of Anisotropic Transmitters by Voronoi-like Structures
Martin Held and Peter Palfrader
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}, }
Ede&21
Implementing Straight Skeletons with Exact Arithmetic: Challenges and Experiences
Günther Eder, Martin Held, and Peter Palfrader
Computational Geometry: Theory and Applications, 96, June 2021
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

Ede&20d
Salzburg Database of Polygonal Data: Polygons and Their Generators
Günther Eder, Martin Held, Steinþór Jasonarson, Philipp Mayer, and Peter Palfrader
Data in Brief, 31:105984, August 2020
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}, }
Ede&20c
Computing Low-Cost Convex Partitions for Planar Point Sets Based on Tailored Decompositions
Günther Eder, Martin Held, Stefan de Lorenzo, and Peter Palfrader
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
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}, }
EdeHP20a
On Implementing Straight Skeletons: Challenges and Experiences
Günther Eder, Martin Held, and Peter Palfrader
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
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}, }
EdeHP20c
Step-By-Step Straight Skeletons
Günther Eder, Martin Held, and Peter Palfrader
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
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}, }
Ede&20a
On Generating Polygons: Introducing the Salzburg Database
Günther Eder, Martin Held, Steinþór Jasonarson, Philipp Mayer, and Peter Palfrader
In Proceedings of the 36th European Workshop on Computational Geometry (EuroCG 2020), pages 75:1–75:7, Würzburg, Germany, March 2020
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}, }
EdeHP20b
Experimental Evaluation of Straight Skeleton Implementations Based on Exact Arithmetic
Günther Eder, Martin Held, and Peter Palfrader
In Proceedings of the 36th European Workshop on Computational Geometry (EuroCG 2020), pages 40:1–40:8, Würzburg, Germany, March 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

EdeHP19a
Computing the Straight Skeleton of an Orthogonal Monotone Polygon in Linear Time
Günther Eder, Martin Held, and Peter Palfrader
In Proceedings of the 35th European Workshop on Computational Geometry (EuroCG 2019), Utrecht, Netherlands, March 2019
We introduce a simple algorithm to construct the straight skeleton of an n-vertex orthogonal monotone polygon in optimal \mathcal{O}(n) 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}, }
EdeHP19b
Min-/Max-Volume Roofs Induced by Bisector Graphs of Polygonal Footprints of Buildings
Günther Eder, Martin Held, and Peter Palfrader
International Journal of Computational Geometry & Applications, 28(4):309–340, 2019
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 \mathcal{O}(n^3 \log n) time for a simple polygon with n 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}, }
EdeHP19c
Recognizing Geometric Trees as Positively Weighted Straight Skeletons and Reconstructing Their Input
Günther Eder, Martin Held, and Peter Palfrader
International Journal of Computational Geometry & Applications, 29(03):251–267, 2019
We extend results by Biedl et al. (ISVD'13) on the recognition and reconstruction of straight skeletons: Given a geometric tree G, can we recognize whether G resembles a weighted straight skeleton \mathcal{S} and, if so, can we reconstruct an appropriate polygonal input P and an appropriate positive weight function \sigma such that \mathcal{S}(P,\sigma)=G? We show that a solution polygon P and a weight function \sigma can be found in O(n) time and space for a geometric tree G with n faces if at most one node of G has two incident edges that span an angle greater than \pi. In addition, we show that G implicitly encodes enough information such that all other weighted bisectors of any solution P can be obtained from G without explicitly computing P.
@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}, }
HePa19a
Straight Skeletons and Mitered Offsets of Polyhedral Terrains in 3D
Martin Held and Peter Palfrader
Computer-Aided Design and Applications, 16(4):611–619, 2019
We present a simple algorithm to compute the straight skeleton and mitered offset surfaces of a polyhedral terrain in 3D, i.e., of a z-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 \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.
@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}, }
HePa19b
Skeletal Structures for Modeling Generalized Chamfers and Fillets in the Presence of Complex Miters
Martin Held and Peter Palfrader
Computer-Aided Design and Applications, 16(4):620–627, 2019
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

EdeHP18a
Parallelized Ear Clipping for the Triangulation and Constrained Delaunay Triangulation of Polygons
Günther Eder, Martin Held, and Peter Palfrader
Computational Geometry: Theory and Applications, 73:15–23, August 2018
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 2–3 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}, }
HePa18a
Straight Skeletons and Mitered Offsets of Polyhedral Terrains in 3D
Martin Held and Peter Palfrader
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}, }
HePa18b
Skeletal Structures for Modeling Complex Chamfers and Fillets
Martin Held and Peter Palfrader
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

HePa17b
Straight Skeletons with Additive and Multiplicative Weights and Their Application to the Algorithmic Generation of Roofs and Terrains
Martin Held and Peter Palfrader
Computer-Aided Design, 92:33–41, November 2017
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.
@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}, }
BieHP16a
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}, }
HePa17a
Straight Skeletons of Monotone Surfaces in Three-Space
Martin Held and Peter Palfrader
In Proceedings of the 33rd 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 33rd European Workshop on Computational Geometry (EuroCG 2017)}, year = {2017}, address = {Malmö, Sweden}, month = {April}, }

2016

Palfrader16
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}, }
EdeHP16a
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}, }
HePa16a
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}, }
HelHP16a
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

Aic&-GD15
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}, }
EdeHP15b
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}, }
HelHP15a
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}, }
HelHP15b
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}, }
EdeHP15a
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}, }
Bie&15a
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}, }
Bie&15b
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}, }
PaHe15
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

BieHP14b
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}, }
PaHe14
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}, }
Bie&14
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].}, }
BieHP14
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

Palfrader13
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}, }
Bie&13
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

PalHH12
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: