The predicates for the Voronoi diagram of ellipses

This paper examines the computation of the Voronoi dia-gram of a set of ellipses in the Euclidean plane. We propose the first complete algorithms, under the exact computation paradigm, for the predicates of an incremental algorithm: κ1 decides which one of 2 given ellipses is closest to a given exterior point; κ2 decides the position of a query ellipse rel-ative to an external bitangent line of 2 given ellipses; κ3 decides the position of a query ellipse relative to a Voronoi circle of 3 given ellipses; κ4 determines the type of conflict between a Voronoi edge, defined by 4 given ellipses, and a query ellipse. The paper is restricted to non-intersecting ellipses, but the extension to arbitrary ones is possible. The ellipses are input in parametric representation or con-structively in terms of their axes, center and rotation. For κ1 and κ2 we derive optimal algebraic conditions, solve them exactly and provide efficient implementations in C++. For κ3 we compute a tight bound on the number of complex tri-tangent circles and use the parametric form of the ellipses in order to design an exact subdivision-based algorithm, which is implemented on Maple. This approach essentially answers κ4 as well. We conclude with current work on optimizing κ3 and implementing it in C++