Publications
2019
Computation and Recognition of Weighted Skeletal
Structures in the Plane
Günther Eder
PhD thesis, University of Salzburg, Salzburg, Austria, July 2019
@phdthesis{Eder19,
author = {Günther Eder},
title = {{C}omputation and {R}ecognition of {W}eighted {S}keletal {S}tructures in the {P}lane},
school = {University of Salzburg},
year = {2019},
address = {Salzburg, Austria},
month = {July},
url = {https://geder.at/research/2019/geder-phdthesis-short.pdf},
}
Computing the Straight Skeleton of an Orthogonal Monotone
Polygon in Linear Time
Günther Eder, Martin Held, and Peter Palfrader
In Proceedings of the 35st 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 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 35st European Workshop on Computational Geometry (EuroCG 2019)},
year = {2019},
address = {Utrecht, Netherlands},
month = {March},
}
Weighted Voronoi Diagrams in the Maximum Norm
Günther Eder and Martin Held
International Journal of Computational Geometry &
Applications, 29(03):239–250, 2019
We consider multiplicatively weighted points, axis-aligned rectangular boxes and axis- aligned straight-line segments in the plane as input sites and study Voronoi diagrams of these sites in the maximum norm. For n weighted input sites we establish a tight Θ(n²) worst-case bound on the combinatorial complexity of their Voronoi diagram and introduce an incremental algorithm that allows its computation in O(n² log n) time. Our approach also yields a truly simple O(n log n) algorithm for solving the one-dimensional version of this problem, where all weighted sites lie on a line.
@article{EdHe19a,
author = {Eder, Günther and Held, Martin},
title = {{W}eighted {V}oronoi {D}iagrams in the {M}aximum {N}orm},
journal = {International Journal of Computational Geometry \& Applications},
year = {2019},
volume = {29},
number = {03},
pages = {239-250},
doi = {10.1142/S0218195919500079},
eprint = {https://doi.org/10.1142/S0218195918500097},
url = {https://doi.org/10.1142/S0218195918500097},
}
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 S and, if so, can we reconstruct an appropriate polygonal input P and an appropriate positive weight function σ such that S(P, σ) = G? We show that a solution polygon P and a weight function σ 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 π. 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{EdeHP19b,
author = {Eder, Günther and Held, Martin and Palfrader, Peter},
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},
eprint = {https://doi.org/10.1142/S0218195919500080},
url = {https://doi.org/10.1142/S0218195919500080},
}
2018
Weighted Voronoi Diagrams in the L
-Norm
Günther Eder and Martin Held
In Proceedings of the 7th Young Researchers Forum (CG Week
2018), Budapest, Hugary, June 2018
We study Voronoi diagrams of n weighted points in the plane in the maximum norm. We establish a tight Θ(n²) worst-case combinatorial bound for such a Voronoi diagram and introduce an incremental construction algorithm that allows its computation in O(n² log n) time.
@inproceedings{EdHe18b,
author = {Günther Eder and Martin Held},
title = {{W}eighted {V}oronoi {D}iagrams in the {L}$_\infty$-{N}orm},
booktitle = {Proceedings of the 7th Young Researchers Forum (CG Week 2018)},
year = {2018},
address = {Budapest, Hugary},
month = {June},
}
Computing Positively Weighted Straight Skeletons of
Simple Polygons based on Bisector Arrangement
Günther Eder and Martin Held
Information Processing Letters, 132:28 – 32, 2018
We extend the work by Huber and Held (IJCGA 2012) on straight-skeleton computation based on motorcycle graphs to positively weighted skeletons. Resorting to a line arrangement induced by the r reflex vertices of a simple n-vertex polygon P allows to compute the weighted straight skeleton of P in O(n² + r³/k + nr log n) time and O(n + kr) space, for an arbitrary positive integer k with 1 ≤ k ≤ r.
@article{EdHe18a,
author = {Günther Eder and Martin Held},
title = {{C}omputing {P}ositively {W}eighted {S}traight {S}keletons of {S}imple {P}olygons based on {B}isector {A}rrangement},
journal = {Information Processing Letters},
year = {2018},
volume = {132},
pages = {28 - 32},
issn = {0020-0190},
doi = {10.1016/j.ipl.2017.12.001},
keywords = {Computational geometry, Weighted straight skeleton, Motorcycle graph, Wavefront propagation, Line arrangement},
url = {http://www.sciencedirect.com/science/article/pii/S0020019017302156},
}
Parallelized ear clipping for the triangulation and constrained
delaunay triangulation of polygons
Günther Eder, Martin Held, and Peter Palfrader
Computational Geometry, 73:15–23, 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 = {Parallelized ear clipping for the triangulation and constrained Delaunay triangulation of polygons},
journal = {Computational Geometry},
year = {2018},
volume = {73},
pages = {15-23},
issn = {0925-7721},
doi = {10.1016/j.comgeo.2018.01.004},
keywords = {Polygon triangulation, Constrained Delaunay triangulation (CDT), Parallelization, Multi-core, Ear-clipping},
url = {https://www.sciencedirect.com/science/article/pii/S092577211830004X},
}
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(04):309–340, 2018
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 𝒪(n^3 log n) time for a simple polygon with n vertices.
@article{EdeHP18b,
author = {Eder, Günther and Held, Martin and Palfrader, Peter},
title = {Min-/Max-Volume Roofs Induced by Bisector Graphs of Polygonal Footprints of Buildings},
journal = {International Journal of Computational Geometry \& Applications},
volume = {28},
number = {04},
pages = {309-340},
year = {2018},
doi = {10.1142/S0218195918500097},
url = {https://doi.org/10.1142/S0218195918500097},
eprint = {https://doi.org/10.1142/S0218195918500097},
}
2017
Computing Positively Weighted Straight Skeletons of
Simple Polygons Using an Induced Line Arrangement
Günther Eder and Martin Held
In Proceedings of the 27th Spanish Meeting on Computational
Geometry (EGC 2017), Alicante, Spain, June 2017
We extend the work by Huber and Held (IJCGA 2012) on straight-skeleton computation based on motorcycle graphs to positively weighted skeletons. Resorting to a line arrangement induced by the r reflex vertices of a simple n-vertex polygon P allows to compute the weighted straight skeleton of P in O(n² + r³/k + nr log n) time and O(n + kr) space, for an arbitrary positive integer k with 1 ≤ k ≤ r.
@inproceedings{EdHe17a,
title = {{C}omputing {P}ositively {W}eighted {S}traight {S}keletons of {S}imple {P}olygons {U}sing an {I}nduced {L}ine {A}rrangement},
author = {Günther Eder and Martin Held},
booktitle = {Proceedings of the 27th Spanish Meeting on Computational Geometry (EGC 2017)},
year = {2017},
address = {Alicante, Spain},
month = {June},
}
2016
Bisector Graphs for Min-/Max-Volume Roofs over Simple
Polygons
Günther Eder, Martin Held, and Peter Palfrader
In Proceedings of the 32st European Workshop on Computational
Geometry (EuroCG 2016), Lugano, Switzerland, March 2016
Piecewise-linear terrains (``roofs'') over simple polygons were studied by Aichholzer et al. (
) 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
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 32st European Workshop on Computational Geometry (EuroCG 2016)},
year = {2016},
address = {Lugano, Switzerland},
month = {March},
}
2015
Experiments on Parallel Polygon Triangulation Using Ear
Clipping
Günther Eder, Martin Held, and Peter Palfrader
In Proceedings of the 4th Young Researchers Forum (CG Week
2015), pages 18–19, Eindhoven, Netherlands, June 2015
We present an experimental study of different strate- gies 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 in- side the polygon. Extensive tests on thousands of sam- ple polygons indicate that about 50% 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 differ- ent on-core approaches to parallelizing ear clipping and report on our experimental findings. Extensive tests show that the most promising method achieves an av- erage 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 Young Researchers Forum (CG Week 2015)},
year = {2015},
address = {Eindhoven, Netherlands},
month = {June},
pages = {18-19},
}
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
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},
}
2014
Parallel Triangulation of Polygons
Günther Eder
Master's thesis, Univeristy of Salzburg, July 2014
In this work we review five different triangulation algorithms and present two of our own. First, two well known algorithms are surveyed: ear-clipping and monotone subdivision. Then, three constrained Delaunay triangulation algorithms are discussed in detail: the first uses a Fortune-like sweep-line approach, the second uses a randomized incremental construction method, and the third is constructing the triangulation in parallel on the GPU. We also present our two parallel ear-clipping methods. One is a divide and conquer approach where the simple input polygon is divided in linear time. The other is a mark and cut extension which uses a sequential mark phase and a parallel cut phase. Both are tested extensively and the results are discussed.
@mastersthesis{Eder14,
author = {Günther Eder},
title = {{P}arallel {T}riangulation of {P}olygons},
school = {Univeristy of Salzburg},
year = {2014},
month = {July},
}