The predicates of the Apollonius diagram: Algorithmic analysis and implementation

We study the predicates involved in an efficient dynamic algorithm for computing the Apollonius diagram in the plane. also known as the additively weighted Voronoi diagram. We present a complete algorithmic analysis of these predicates, some of which are reduced to simpler and more easily computed primitives. This gives rise to ail exact and efficient implementation of the algorithm, that handles all special cases. Among our tools we distinguish ail inversion transformation and an infinitesimal perturbation for handling degeneracies. The implementation of the predicates requires certain algebraic operations. In Studying the latter, we aim at minimizing the algebraic degree of the predicates and the number of arithmetic operations; this twofold optimization corresponds to reducing bit complexity. The proposed algorithms are based oil static Sturm sequences. Multivariate resultants provide a deeper understanding of the predicates and are compared against our methods. We expect that our algebraic techniques are sufficiently powerful and general to be applied to a number of analogous geometric problems on curved objects.. Their efficiency, and that of the overall implementation, are illustrated by a series of numerical experiments. Our approach can be immediately extended to the incremental construction of abstract Voronoi diagrams for various classes of objects. (c) 2005 Elsevier- B.V. All rights reserved.