@COMMENT {Autogenerated file by bib2html.pl version 0.94}
@Article{ett-ijcga-2007,
author = {Ioannis~Z. Emiris and Elias~P. Tsigaridas and George
Tzoumas},
title = {{Predicates for the exact Voronoi diagram of
ellipses under the Euclidean metric}},
journal = IJCGA,
year = 2008,
volume = 18,
number = 6,
pages = "567--597",
editor = {N. Amenta and O. Cheong},
note = {(special issue devoted to SoCG 2007)},
abstract = " This article examines the computation of the
Voronoi diagram of a set of ellipses in the
Euclidean plane. We propose the first complete
methods, under the exact computation paradigm, for
the predicates of an incremental algorithm: \ka
decides which one of two given ellipses is closest
to a given exterior point; \kb decides the position
of a query ellipse relative to an external bitangent
line of two given ellipses; \kc decides the position
of a query ellipse relative to a Voronoi circle of
three given ellipses; \kd determines the type of
conflict between a Voronoi edge, defined by four
given ellipses, and a query ellipse. The article is
restricted to non-intersecting ellipses, but the
extension to arbitrary ones is possible. The
ellipses are input in parametric representation,
i.e. constructively in terms of their axes, center
and rotation. For \ka and \kb we derive optimal
algebraic conditions and provide efficient
implementations in \cpp. For \kc we compute a tight
bound on the number of complex tritangent circles
and design an exact symbolic-numeric algorithm,
which is implemented in \maple. This essentially
answers \kd as well. We conclude with current work
on optimizing \kc and on its implementation in
\cpp.",
}