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.