Files:
[PDF] 479.2kB [gzipped postscript] 467.7kB
Abstract:
We present a C++ open-source implementation of an incremental algorithm for the computation of the Voronoi diagram of ellipses in the Euclidean plane. This is the first complete implementation, under the exact computation paradigm, for the given problem. It is based on the \cgal package for the Apollonius diagram in the plane: exploiting the generic programming principle, our main additions concern the predicates. The ellipses are input in parametric representation, which allows us to develop a GUI for input and output. The software concerns non-intersecting ellipses, but the extension to the general case is possible. We develop practical algebraic methods, including an interval Newton solver, bivariate polynomial interpolation, and trivariate system resultant computation, and exploit the factorization of resultants in order to arrive at an efficient and exact C++ implementation of \incircle. The code is up to two orders of magnitude slower than the \cgal Apollonius package on circles, which comes as no surprise. We also test different sets of ellipses; as a ballmark estimate, the current version spends about a second to insert a new ellipse, when few degeneracies occur. The software is connected to algebraic library \synaps and, through it, to libraries \mpfr and \ntl, hence illustrating the concept of algebraic support for geometric computing; it is targeted for inclusion in the \cgal library.
BibTeX:
@inproceedings{ett-spm-2009,
author = {Ioannis Z. Emiris and Elias P. Tsigaridas and George
M. Tzoumas},
title = {{Exact Delaunay graph of smooth convex
pseudo-circles: general predicates, and
implementation for ellipses}},
booktitle = {Proc. of ACM Symp. on Solid and Physical Modeling
(SPM)},
year = 2009,
pages = {211--222},
ee = {http://doi.acm.org/10.1145/1629255.1629282},
editor = {W.F. Bronsvoort and D. Gonsor and W.C. Regli and
T.A. Grandine and J.H. Vandenbrande and J. Gravesen
and J. Keyser},
date = "oct",
bibsource = {DBLP, http://dblp.uni-trier.de},
abstract = " We present a C++ open-source implementation of an
incremental algorithm for the computation of the
Voronoi diagram of ellipses in the Euclidean plane.
This is the first complete implementation, under the
exact computation paradigm, for the given problem.
It is based on the \cgal\ package for the Apollonius
diagram in the plane: exploiting the generic
programming principle, our main additions concern
the predicates. The ellipses are input in
parametric representation, which allows us to
develop a GUI for input and output. The software
concerns non-intersecting ellipses, but the
extension to the general case is possible. We
develop practical algebraic methods, including an
interval Newton solver, bivariate polynomial
interpolation, and trivariate system resultant
computation, and exploit the factorization of
resultants in order to arrive at an efficient and
exact C++ implementation of \incircle. The code is
up to two orders of magnitude slower than the \cgal\
Apollonius package on circles, which comes as no
surprise. We also test different sets of ellipses;
as a ballmark estimate, the current version spends
about a second to insert a new ellipse, when few
degeneracies occur. The software is connected to
algebraic library \synaps\ and, through it, to
libraries \mpfr\ and \ntl, hence illustrating the
concept of algebraic support for geometric
computing; it is targeted for inclusion in the
\cgal\ library. ",
}
Generated by bib2html.pl (written by Patrick Riley , modified by Elias ) on Wed Oct 23, 2019 21:41:02