@STRING{cad = {Computer-Aided Design} }
@STRING{cada = {Computer-Aided Design and Applications} }
@STRING{cadc = {Computer-Aided Design Conference} }
@STRING{cccg = {Canadian Conference on Computational Geometry} }
@STRING{cgta = {Computational Geometry: Theory and Applications} }
@STRING{cgyrf = {Computational Geometry Week: Young Reseachers Forum} }
@STRING{dagstuhl= {Schloss Dagstuhl--Leibniz-Zentrum für Informatik} }
@STRING{dib = {Data in Brief} }
@STRING{esa = {Annual European Symposium on Algorithms} }
@STRING{eurocg = {European Workshop on Computational Geometry} }
@STRING{gd = {International Symposium on Graph Drawing \& Network
Visualization} }
@STRING{ijcga = {International Journal of Computational Geometry \&
Applications} }
@STRING{ipl = {Information Processing Letters} }
@STRING{isaac = {International Symposium on Algorithms and Computation} }
@STRING{jea = {ACM Journal of Experimental Algorithmics} }
@STRING{lncs = {Lecture Notes in Computer Science} }
@STRING{proc = {Proceedings of the} }
@STRING{socg = {International Symposium on Computational Geometry} }
@STRING{sv = {Springer-Verlag} }
@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 = proc # { 23rd } # gd # { (GD 2015)},
year = {2015},
address = {Los Angeles, CA, USA},
month = sep,
publisher = sv,
series = lncs,
volume = {9411},
abstract = {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.},
doi = {10.1007/978-3-319-27261-0_28},
eprint = {1508.01076},
eprinttype = {arxiv}
}
@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 = cgta,
year = {2015},
month = feb,
number = {2},
pages = {120--133},
volume = {48},
abstract = {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.},
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}
}
@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 = ipl,
year = {2015},
month = feb,
number = {2},
pages = {243--247},
volume = {115},
abstract = {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.},
doi = {10.1016/j.ipl.2014.09.021}
}
@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 = proc # { 30th } # eurocg # { (EuroCG 2014)},
year = {2014},
address = {Ein-Gedi, Israel},
month = mar,
note = {An extended version appeared in IPL 15(2):243–247, Feb
2015 [Bie\&15b].},
abstract = {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&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 = proc # { 25th } # cccg # { (CCCG 2013)},
year = {2013},
address = {Waterloo, ON, Canada},
month = aug,
note = {An extended version appeared in CGTA 48(2):120–133, Feb
2015 [Bie\&15a].},
pages = {13--18},
abstract = {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{ BieHP14b,
title = {{P}lanar {M}atchings for {W}eighted {S}traight
{S}keletons},
author = {Therese Biedl and Stefan Huber and Peter Palfrader},
booktitle = proc # { 25th } # isaac # { (ISAAC 2014)},
year = {2014},
address = {Jeonju, Korea},
editor = {Hee-Kap Ahn and Chan-Su Shin},
month = dec,
pages = {117--127},
publisher = sv,
series = lncs,
volume = {8889},
abstract = {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.},
doi = {10.1007/978-3-319-13075-0_10}
}
@Article{ BieHP16a,
author = {Therese Biedl and Stefan Huber and Peter Palfrader},
title = {{P}lanar {M}atchings for {W}eighted {S}traight
{S}keletons},
journal = ijcga,
year = {2016},
volume = {26},
number = {3 \& 4},
pages = {221--229},
month = sep # { \& } # dec,
note = {published } # apr # { 2017},
abstract = {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.},
doi = {10.1142/S0218195916600050}
}
@InProceedings{ BieHP14,
title = {{S}table {R}oommates for {W}eighted {S}traight
{S}keletons},
author = {Therese Biedl and Stefan Huber and Peter Palfrader},
booktitle = proc # { 30th } # eurocg # { (EuroCG 2014)},
year = {2014},
address = {Ein-Gedi, Israel},
month = mar,
note = {An extended version appeared in Proceedings of ISAAC 2014
[BieHP14b].},
abstract = {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.}
}
@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 = cgta,
year = {2018},
volume = {73},
pages = {15--23},
month = aug,
abstract = {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.},
doi = {10.1016/j.comgeo.2018.01.004}
}
@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 = proc # { 32nd } # eurocg # { (EuroCG 2016)},
year = {2016},
address = {Lugano, Switzerland},
month = mar,
abstract = {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{ 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 = proc # { 31st } # eurocg # { (EuroCG 2015)},
year = {2015},
address = {Ljubljana, Slovenia},
month = mar,
pages = {220--223},
abstract = {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{ 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 = proc # { 4th } # cgyrf # { (CG-YRF 2015)},
year = {2015},
address = {Eindhoven, Netherlands},
month = jun,
pages = {18--19},
abstract = {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.}
}
@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 = cada,
year = {2016},
number = {5},
pages = {712--721},
volume = {13},
abstract = {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.},
doi = {10.1080/16864360.2016.1150718}
}
@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 = proc # { 12th } # cadc # { (CAD 2015)},
year = {2015},
address = {London, United Kingdom},
month = jun,
note = {An extended version is to appear in CADA.},
pages = {264--268},
doi = {10.14733/cadconfP.2015.264-268}
}
@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 = proc # { 4th } # cgyrf # { (CG-YRF 2015)},
year = {2015},
address = {Eindhoven, Netherlands},
month = jun,
note = {An extended version is to appear in CADA.},
pages = {22--23},
abstract = {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
\emph{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{ HePa17a,
author = {Martin Held and Peter Palfrader},
title = {{S}traight {S}keletons of {M}onotone {S}urfaces in
{T}hree-{S}pace},
booktitle = proc # { 33rd } # eurocg # { (EuroCG 2017)},
year = {2017},
address = {Malmö, Sweden},
month = apr,
abstract = {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{ HePa16a,
title = {{A}dditive {W}eights for {S}traight {S}keletons},
author = {Martin Held and Peter Palfrader},
booktitle = proc # { 32nd } # eurocg # { (EuroCG 2016)},
year = {2016},
address = {Lugano, Switzerland},
month = mar,
abstract = {We introduce an \emph{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.}
}
@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 = cad,
year = {2017},
volume = {92},
pages = {33--41},
month = nov,
issn = {0010-4485},
abstract = {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.},
doi = {10.1016/j.cad.2017.07.003},
eprint = {1604.03362},
eprinttype = {arxiv}
}
@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 = apr,
abstract = {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.},
url = {https://www.palfrader.org/research/k/Palfrader16.pdf}
}
@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 = sep,
abstract = {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, \textsc{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 --- \emph{On Computing Straight Skeletons by
Means of Kinetic Triangulations}).},
url = {https://www.palfrader.org/research/2013/master-thesis.pdf}
}
@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 = cada,
year = {2015},
month = feb,
number = {4},
pages = {414--424},
volume = {12},
abstract = {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.},
doi = {10.1080/16864360.2014.997637}
}
@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 = proc # { 11th } # cadc # { (CAD 2014)},
year = {2014},
address = {Hong Kong, China},
month = jun,
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}
}
@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 = proc # { 20th } # esa # { (ESA 2012)},
year = {2012},
address = {Ljubljana, Slovenia},
editor = {Leah Epstein and Paolo Ferragina},
month = sep,
pages = {766--777},
publisher = sv,
series = lncs,
volume = {7501},
abstract = {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,
\textsc{Surfer}, runs in $\mathcal{O}(n \log n)$ time on
average, and (3) that it clearly is the fastest
straight-skeleton code currently available.},
doi = {10.1007/978-3-642-33090-2_66}
}
@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 = ijcga,
year = {2019},
volume = {28},
number = {4},
pages = {309--340},
abstract = {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.},
doi = {10.1142/S0218195918500097}
}
@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 = proc # { 15th } # cadc # { (CAD 2018)},
year = {2018},
pages = {37--41},
address = {Paris, France},
month = jul,
doi = {10.14733/cadconfP.2018.37-41}
}
@InProceedings{ HePa18b,
author = {Martin Held and Peter Palfrader},
title = {{S}keletal {S}tructures for {M}odeling {C}omplex
{C}hamfers and {F}illets},
booktitle = proc # { 15th } # cadc # { (CAD 2018)},
year = {2018},
pages = {42--46},
address = {Paris, France},
month = jul,
doi = {10.14733/cadconfP.2018.42-46}
}
@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 = cada,
year = {2019},
volume = {16},
number = {4},
pages = {611--619},
abstract = {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.},
doi = {10.14733/cadaps.2019.611-619}
}
@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 = cada,
year = {2019},
volume = {16},
number = {4},
pages = {620--627},
abstract = {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.},
doi = {10.14733/cadaps.2019.620-627}
}
@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 = proc # { 35th } # eurocg # { (EuroCG 2019)},
year = {2019},
address = {Utrecht, Netherlands},
month = mar,
abstract = {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.}
}
@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 = ijcga,
year = {2019},
volume = {29},
number = {03},
pages = {251--267},
abstract = {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$.},
doi = {10.1142/S0218195919500080}
}
@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 = proc # { 36th } # eurocg # { (EuroCG 2020)},
year = {2020},
pages = {40:1--40:8},
address = {Würzburg, Germany},
month = mar,
abstract = {We present C++ implementations of two algorithms for
computing straight skeletons in the plane, based on exact
arithmetic. One code, named \textsc{Surfer2}, can handle
multiplicatively weighted planar straight-line graphs
(PSLGs) while our second code, \textsc{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
\textsc{Surfer2} and \textsc{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{ 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 = proc # { 36th } # eurocg # { (EuroCG 2020)},
year = {2020},
pages = {75:1--75:7},
address = {Würzburg, Germany},
month = mar,
abstract = {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{ 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 } # socg # { (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 = jun,
publisher = dagstuhl,
abstract = {We present C++ implementations of two algorithms for
computing straight skeletons in the plane, based on exact
arithmetic. One code, named \textsc{Surfer2}, can handle
multiplicatively weighted planar straight-line graphs
(PSLGs) while our second code, \textsc{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
\textsc{Surfer2} and \textsc{Monos} to the
straight-skeleton package included in CGAL. It is not
surprising that our special-purpose code \textsc{Monos}
outperforms CGAL's straight-skeleton implementation. But
our tests provide ample evidence that also \textsc{Surfer2}
can be expected to be faster and to consume significantly
less memory than the CGAL code. And, of course,
\textsc{Surfer2} is more versatile because it can handle
multiplicative weights and general PSLGs as input. Thus,
\textsc{Surfer2} currently is the fastest and most general
straight-skeleton code available.},
doi = {10.4230/LIPIcs.SoCG.2020.38},
isbn = {978-3-95977-143-6},
issn = {1868-8969},
urn = {urn:nbn:de:0030-drops-121964}
}
@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 } # socg # { (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 = jun,
publisher = dagstuhl,
abstract = {We present two software packages for computating straight
skeletons: \textsc{Monos}, our implementation of an
algorithm by Biedl et al.~(2015), computes the straight
skeleton of a monotone input polygon, and \textsc{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.},
doi = {10.4230/LIPIcs.SoCG.2020.76},
isbn = {978-3-95977-143-6},
issn = {1868-8969},
urn = {urn:nbn:de:0030-drops-122343}
}
@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 = jea,
year = {2022},
volume = {27},
month = dec,
abstract = {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.},
doi = {10.1145/3500913}
}
@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 } # socg # { (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 = jun,
publisher = dagstuhl,
abstract = {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.},
doi = {10.4230/LIPIcs.SoCG.2020.85},
isbn = {978-3-95977-143-6},
issn = {1868-8969},
urn = {urn:nbn:de:0030-drops-122438}
}
@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 = dib,
year = {2020},
volume = {31},
pages = {105984},
month = aug,
issn = {2352-3409},
abstract = {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.},
doi = {10.1016/j.dib.2020.105984}
}
@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 = cgta,
year = {2021},
volume = {96},
month = jun,
issn = {0925-7721},
abstract = {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.},
doi = {10.1016/j.comgeo.2021.101760}
}
@InProceedings{ HePa21a,
author = {Martin Held and Peter Palfrader},
title = {{Modeling Coverage Areas of Anisotropic Transmitters by
Voronoi-like Structures}},
booktitle = proc # { 18th } # cadc # { (CAD 2021)},
year = {2021},
pages = {283--287},
address = {Barcelona, Spain},
month = jul,
doi = {10.14733/cadconfP.2021.283-287}
}
@Article{ HePa22a,
author = {Martin Held and Peter Palfrader},
title = {{Modeling Coverage Areas of Anisotropic Transmitters by
Voronoi-like Structures}},
journal = cada,
year = {2022},
volume = {19},
number = {5},
pages = {967--976},
abstract = {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.},
doi = {10.14733/cadaps.2022.967-976}
}