@inproceedings{aahw-emacc-11,
author = {O. Aichholzer and W. Aigner and T. Hackl and N. Wolpert},
title = {{{Exact medial axis computation for circular arc
boundaries}}},
booktitle = {Proc. $7^{th}$ International Conference on Curves and
Surfaces 2010 (Avignon, France), LNCS 6920},
editor = {J.D. Boissonat and M.L. Mazure and L.L. Schumaker},
address = {Avignon, France},
publisher = {Springer},
series = {Lecture Notes in Computer Science (LNCS)},
number = {6920},
category = {3b},
thackl_label = {26C},
pages = {28--42},
year = {2011},
pdf = {/files/publications/geometry/aahw-emacc-11.pdf},
abstract = {We propose a method to compute the algebraically correct
medial axis for simply connected planar domains which are
given by boundary representations composed of rational
circular arcs. The algorithmic approach is based on the
Divide-and-Conquer paradigm. However, we show how to avoid
inaccuracies in the medial axis computations arising from a
non-algebraic biarc construction of the boundary. To this
end we introduce the Exact Circular Arc Boundary
representation (ECAB), which allows algebraically exact
calculation of bisector curves. Fractions of these bisector
curves are then used to construct the exact medial axis. We
finally show that all necessary computations can be
performed over the fild of rational numbers with a small
number of adjoint square-roots.},
originalfile = {/geometry/cggg.bib}
}
@article{aaahjpr-dcvdr-10,
author = {O. Aichholzer and W. Aigner and F. Aurenhammer and
T.~Hackl and B.~J\"uttler and E.~Pilgerstorfer and M.~Rabl},
title = {{{Divide-and conquer for {V}oronoi diagrams revisited}}},
journal = {Computational Geometry: Theory and Applications},
note = {Special Issue on the 25th Annual Symposium on
Computational Geometry (SoCG'09)},
pages = {688--699},
volume = {43},
number = {8},
category = {3a},
doi = {http://dx.doi.org/10.1016/j.comgeo.2010.04.004},
year = 2010,
pdf = {/files/publications/geometry/aaahjpr-dcvdr-09b.pdf},
thackl_label = {15J},
abstract = {We show how to divide the edge graph of a Voronoi diagram
into a tree that corresponds to the medial axis of an
(augmented) planar domain. Division into base cases is then
possible, which, in the bottom-up phase, can be merged by
trivial concatenation. The resulting construction
algorithm---similar to Delaunay triangulation methods---is
not bisector-based and merely computes dual links between
the sites, its atomic steps being inclusion tests for sites
in circles. This guarantees computational simplicity and
numerical stability. Moreover, no part of the Voronoi
diagram, once constructed, has to be discarded again. The
algorithm works for polygonal and curved objects as sites
and, in particular, for circular arcs which allows its
extension to general free-form objects by Voronoi diagram
preserving and data saving biarc approximations. The
algorithm is randomized, with expected runtime $O(n\log n)$
under certain assumptions on the input data. Experiments
substantiate an efficient behavior even when these
assumptions are not met. Applications to offset
computations and motion planning for general objects are
described.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{aaahjpr-dcvdr-09b,
author = {O. Aichholzer and W.~Aigner and F. Aurenhammer and
T.~Hackl and B.~J{\"u}ttler and E.~Pilgerstorfer and
M.~Rabl},
title = {{{Divide-and-Conquer for Voronoi Diagrams Revisited}}},
booktitle = {$25^{th}$ Ann. ACM Symp. Computational Geometry},
category = {3b},
pages = {189--197},
pdf = {/files/publications/geometry/aaahjpr-dcvdr-09b.pdf},
oaich_label = {81b},
thackl_label = {15C},
year = 2009,
address = {Aarhus, Denmark},
abstract = {We propose a simple and practical divide-and-conquer
algorithm for constructing planar Voronoi diagrams. The
novel aspect of the algorithm is its emphasis on the
top-down phase, which makes it applicable to sites of
general shape.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{aaahjpr-dcvdr-09,
author = {O. Aichholzer and W.~Aigner and F. Aurenhammer and
T.~Hackl and B.~J{\"u}ttler and E.~Pilgerstorfer and
M.~Rabl},
title = {{{Divide-and-Conquer for Voronoi Diagrams Revisited}}},
booktitle = {Proc. $25^{th}$ European Workshop on Computational
Geometry EuroCG '09},
category = {3b},
pages = {293--296},
pdf = {/files/publications/geometry/aaahjpr-dcvdr-09.pdf},
oaich_label = {81},
thackl_label = {15C},
year = 2009,
address = {Brussels, Belgium},
abstract = {We propose a simple and practical divide-and-conquer
algorithm for constructing planar Voronoi diagrams. The
novel aspect of the algorithm is its emphasis on the
top-down phase, which makes it applicable to sites of
general shape.},
originalfile = {/geometry/cggg.bib}
}
@article{aaahjr-macpf-08,
author = {O. Aichholzer and W. Aigner and F. Aurenhammer and
T.~Hackl and B.~J{\"u}ttler and M.~Rabl},
title = {{{Medial Axis Computation for Planar Free-Form Shapes}}},
journal = {Computer-Aided Design},
note = {Special issue: {V}oronoi Diagrams and their Applications},
year = 2009,
volume = {41},
category = {3a},
number = {5},
oaich_label = {77},
thackl_label = {11J},
doi = {http://dx.doi.org/10.1016/j.cad.2008.08.008},
pdf = {/files/publications/geometry/aaahjr-macpf-09.pdf},
pages = {339--349},
abstract = {We present a simple, efficient, and stable method for
computing---with any desired precision---the medial axis of
simply connected planar domains. The domain boundaries are
assumed to be given as polynomial spline curves. Our
approach combines known results from the field of geometric
approximation theory with a new algorithm from the field of
computational geometry. Challenging steps are (1) the
approximation of the boundary spline such that the medial
axis is geometrically stable, and (2) the efficient
decomposition of the domain into base cases where the
medial axis can be computed directly and exactly. We solve
these problems via spiral biarc approximation and a
randomized divide \& conquer algorithm.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{aaaj-emact-11,
author = {O. Aichholzer and W. Aigner and F. Aurenhammer and B.
J\"uttler},
title = {{{Exact medial axis computation for triangulated solids with
respect to piecewise linear metrics}}},
booktitle = {Proc. $7^{th}$ International Conference on Curves and
Surfaces 2010 (Avignon, France)},
editor = {J.D. Boissonat and M.L. Mazure and L.L. Schumaker},
address = {Avignon, France},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
number = {6920},
category = {3b},
pages = {1--27},
year = {2011},
pdf = {/files/publications/geometry/aaaj-emact-11.pdf},
abstract = {We propose a novel approach for the medial axis
approximation of triangulated solids by using a polyhedral
unit ball $B$ instead of the standard Euclidean unit ball.
By this means, we compute the exact medial axis
$MA(\Omega)$ of a triangulated solid $\Omega$ with respect
to a piecewise linear (quasi-)metric $d_B$. The obtained
representation of $\Omega$ by the medial axis transform
$MAT(\Omega)$ allows for a convenient computation of the
trimmed offset of $\Omega$ with respect to $d_B$. All
calculations are performed within the field of rational
numbers, resulting in a robust and efficient implementation
of our approach. Adapting the properties of $B$ provides an
easy way to control the level of details captured by the
medial axis, making use of the implicit pruning at flat
boundary features.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{aaadjr-twca-11,
author = {O.~Aichholzer and W.~Aigner and F.~Aurenhammer and
K.\v{C}~Dobi\'a\v{s}ov\'a, B.~J\"uttler and G.~Rote},
title = {{{Triangulations with circular arcs}}},
booktitle = {$19^{th}$ Symposium on Graph Drawing 2011 (Eindhoven, The
Netherlands)},
category = {3b},
pages = {296--307},
year = 2011,
pdf = {/files/publications/geometry/aaadjr-twca-11.pdf},
abstract = {An important objective in the choice of a triangulation of
a given point set is that the smallest angle becomes as
large as possible. In the straight line case, it is known
that the Delaunay triangulation is optimal in this
respect.We propose and study the concept of a circular arc
triangulation, a simple and effective alternative that
offers flexibility for additionally enlarging small
angles.We show that angle optimization and related
questions lead to linear programming problems that can be
formulated as simple graph-theoretic problems, and we
define flipping operations in arc triangles. Moreover,
special classes of arc triangulations are considered, for
applications in graph drawing and finite element methods.},
originalfile = {/geometry/cggg.bib}
}
@article{aaadjr-twca-15,
author = {O.~Aichholzer and W.~Aigner and F.~Aurenhammer and
K.\v{C}~Dobi\'a\v{s}ov\'a, B.~J\"uttler and G.~Rote},
title = {{{Triangulations with circular arcs}}},
category = {3a},
journal = {Journal of Graph Algorithms and Applications},
year = {2015},
volume = {19},
number = {1},
pages = {43--65},
doi = {10.7155/jgaa.00346},
pdf = {/files/publications/geometry/aaadjr_tca_15.pdf},
abstract = {An important objective in the choice of a triangulation of
a given point set is that the smallest angle becomes as
large as possible. In the straight line case, it is known
that the Delaunay triangulation is optimal in this
respect.We propose and study the concept of a circular arc
triangulation, a simple and effective alternative that
offers flexibility for additionally enlarging small
angles.We show that angle optimization and related
questions lead to linear programming problems that can be
formulated as simple graph-theoretic problems, and we
define flipping operations in arc triangles. Moreover,
special classes of arc triangulations are considered, for
applications in finite element methods and graph drawing.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{aaadj-at-10,
author = {O.~Aichholzer and W.~Aigner and F.~Aurenhammer and
K.\v{C}~Dobi\'a\v{s}ov\'a and B.~J\"uttler},
title = {{{Arc Triangulations}}},
booktitle = {Proc. $26^{th}$ European Workshop on Computational
Geometry EuroCG '10},
pages = {17--20},
year = 2010,
address = {Dortmund, Germany},
pdf = {/files/publications/geometry/aaadj-at-10.pdf},
abstract = {The quality of a triangulation is, in many practical
applications, influenced by the angles of its triangles. In
the straight line case, angle optimization is not possible
beyond the Delaunay triangulation. We propose and study the
concept of circular arc triangulations, a simple and
effective alternative that offers flexibility for
additionally enlarging small angles. We show that angle
optimization and related questions lead to linear
programming problems, and we define unique flips in arc
triangulations. Moreover, applications of certain classes
of arc triangulations in the areas of finite element
methods and graph drawing are sketched.},
originalfile = {/geometry/cggg.bib}
}
This file was generated by bibtex2html 1.98.