@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{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{lncs = {Lecture Notes in Computer Science} }
@STRING{proc = {Proceedings of the} }
@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.}
}
@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 # { 33nd } # 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.}
}
@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}
}