THE PREDICATES FOR THE EXACT VORONOI DIAGRAM OF ELLIPSES UNDER THE EUCLIDIEAN METRIC.

This article examines the computation of the Delaunay graph and its dual 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: κ₁ decides which one of two given ellipses is closest to a given exterior point; κ₂ decides the position of a query ellipse relative to an external bitangent line of two given ellipses; κ₃ decides the position of a query ellipse relative to a Voronoi circle of three given ellipses; κ₄ 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 κ₁ and κ₂ we derive algebraic conditions optimal in terms of the degree of the algebraic numbers involved, and provide efficient implementations in C++. For κ₃ 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 κ₄ as well. We conclude with further work on lifting the condition of non-intersecting ellipses. [ABSTRACT FROM AUTHOR]