Karavelas and Emiris consider additively weighted Voronoi diagrams (Voronoi diagrams in which the sites carry weights), and the distance of a point from a site is the Euclidean distance minus the weight of the site. Geometrically, this corresponds to Voronoi diagrams of circles.

In contrast to the classical Voronoi diagram (with weights 0), the bisectors in additively weighted Voronoi diagrams are not straight lines, but algebraic curves. Therefore, the decisions about properties of such Voronoi diagrams become decision problems on the signs of certain real algebraic numbers. The authors review existing comparison methods based on various resultant methods. This approach leads to considering the roots of a polynomial of degree 18. The method proposed by the authors for computing the roots is based on Sturm sequences, and it can be shown to finally lead to the consideration of a polynomial of degree 16. This improvement in the degree of polynomials results in better decision methods, the quality of which can be observed experimentally.

This paper is an interesting combination of algebraic, geometric, and complexity theoretic results. However, the reader would have profited from clearer statements of the problems, for example in section 1.1, where the authors do not deem it necessary to state which variables are considered to be roots of which polynomials.