Olivier Devillers

Menelaos I Karavelas

Monique Teillaud

Qualitative Symbolic Perturbation: Two Applications of a New Geometry-based Perturbation Framework

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

In earlier computational geometry papers, the treatment of degenerate configurations was mainly ignored. However, degenerate situations actually do occur in practice. When data are highly degenerate by nature, a direct handling of special cases in a particular algorithm can be efficient [START_REF] Burnikel | On degeneracy in geometric computations[END_REF]. But in many situations, degeneracies happen only occasionally, and perturbation schemes are an easy and efficient generic solution. Controlled perturbations [START_REF] Mehlhorn | A general approach to the analysis of controlled perturbation algorithms[END_REF] combine increasing arithmetic precision together with actual displacement of the data, and eventually compute a non-degenerate configuration. On the other hand, the use of a symbolic perturbation allows a geometric algorithm or data structure that was originally designed without addressing degeneracies, to still operate on degenerate cases, without concretely modifying the input [START_REF] Edelsbrunner | Simulation of simplicity: A technique to cope with degenerate cases in geometric algorithms[END_REF][START_REF] Yap | A geometric consistency theorem for a symbolic perturbation scheme[END_REF][START_REF] Yap | Symbolic treatment of geometric degeneracies[END_REF]. Actually, similar strategies were often used by earlier implementors of simple geometric algorithms, without identifying them as symbolic perturbations: for instance when incrementally computing a convex hull, when the new inserted point was lying on a facet of the convex hull, the point was decided to be inside the convex hull.

Let us formalize the notions of geometric problem and degeneracy. Let G(u) be a geometric structure depending on some input data u. The input space I to which the input u belongs is usually some space with a natural topology; e.g., if u is a set of n points in the plane, the input space is I = R 2n . The output space O may be more fuzzy since the structure can often be described in various ways; for example, the convex hull of u ∈ R 2n can be defined as a (compact convex) subset of R 2 , then O ⊂ 2 R 2 , or as the finite subset of N containing the indices of the extreme vertices, then O = 2 N . We choose a combinatorial definition of the geometric structure so that the output space is countable; for instance we define a planar Voronoi diagram as the set of triples of indices of points defining Voronoi vertices, i.e., a finite subset of N 3 : O = 2 N 3 . For such a discrete space the usual topology is the trivial topology, i.e., the singleton {x} is a valid neighborhood of point x. In this setting, a degenerate configuration u 0 for the geometric structure G is an input position u 0 where G is not continuous, i.e., not constant since we use the trivial topology on O; for a degenerate configuration u 0 , the geometric structure G(u 0 ) may be undefined (or not uniquely defined).

A symbolic perturbation consists in using as input u for G the values of a continuous function π: I × R ≥0 → I of a parameter ε. This is done in such a way that for ε = 0 the value of π(u 0 , 0) is equal to u 0 , and π(u 0 , ε) is non-degenerate for G for sufficiently small positive values of ε. We define Ĝ as Ĝ(u) = lim ε→0 + G(π(u, ε)). If u 0 is a non-degenerate configuration, i.e., if G is continuous in u 0 , then by continuity Ĝ(u 0 ) = G(u 0 ). Otherwise, G(u 0 ) may be either undefined or different from Ĝ(u 0 ). With a slight abuse of notation, in the rest of this paper we still denote the modified function Ĝ as G.

A symbolic perturbation allows an algorithm that computes G(u) in generic situations to compute G(u 0 ) for the degenerate input u 0 . Most decisions made by the algorithm are usually made by looking at geometric predicates, which are combinations of elementary predicates. An elementary predicate is the sign of a continuous real function of the input, where the output space for the sign function is {-1, 0, 1}. A configuration is algorithmically degenerate, when some predicate used by the algorithm returns 0. When applying a symbolic perturbation, a predicate sign(p(u)) evaluated at u 0 returns the limit of sign(p(π(u 0 , ε))) as ε → 0 + . A perturbation scheme is said to be effective for a predicate sign(p(u)) if for any u 0 the limit exists, and it is non-zero. The perturbed sign of p(u 0 ) is then given by this limit.

The main difficulty when designing a perturbation scheme for G(u) is to find a function π(u 0 , ε), such that the perturbation scheme can be proved to be effective for all relevant functions p(u), and the perturbed predicates are easy to evaluate, e.g., using as few as possible arithmetic operations. The work of designing and proving the effectiveness of a perturbation for G is typically tailored to a specific algorithm for computing the geometric structure G.

In previous works [START_REF] Alliez | Removing degeneracies by perturbing the problem or the world[END_REF][START_REF] Devillers | Perturbations for Delaunay and weighted Delaunay 3D triangulations[END_REF][START_REF] Edelsbrunner | Simulation of simplicity: A technique to cope with degenerate cases in geometric algorithms[END_REF][START_REF] Emiris | A general approach to removing degeneracies[END_REF][START_REF] Seidel | The nature and meaning of perturbations in geometric computing[END_REF], a predicate is the sign of a polynomial P in some input u ∈ R m . The input u is perturbed as an element π(u 0 , ε) of R m whose coordinates are polynomials in u 0 and ε, such that π(u 0 , ε) goes to u 0 when ε → 0 + . The perturbed predicate returns the sign of the limit lim ε→0 + sign(P (π(u 0 , ε))). Since P is a polynomial, P (π(u 0 , ε)) can be rewritten as a polynomial in ε whose monomials in ε are ordered in terms of increasing degree. The constant monomial is actually P (u 0 ), while the signs of the remaining coefficients can be viewed as auxiliary predicates on u 0 . The coefficients of P (π(u 0 , ε)) are evaluated in increasing degrees in ε, until a non-vanishing coefficient is found. The sign of this coefficient is then returned as the value of the predicate sign(P (u 0 )).

Contribution

In this paper we propose QSP (Qualitative Symbolic Perturbation), a new framework for resolving degenerate configurations in geometric computing. Unlike classical symbolic perturbation techniques, QSP resolves degeneracies in a purely geometric manner, and independently of a specific algebraic formulation of the predicate. So, the technique is particularly suitable for predicates whose algebraic description is not unique or too complicated, such as the ones treated in this paper. In fact, QSP can even handle predicates that are signs of non-polynomial functions.

In addition, instead of having a single perturbation parameter that governs the way the input objects or predicates are modified, QSP allows for a sequence of perturbation parameters: conceptually, we symbolically apply the different perturbations one after the other, using a well-defined canonical ordering that corresponds to considering first the biggest perturbation. To achieve termination, we must devise an appropriate sequence of perturbations which guarantees that eventually, i.e., after having perturbed sufficiently many input objects, the degenerate predicate is resolved in a non-degenerate manner. The number of objects that need to be perturbed depends on the specific predicate that we analyze. For example in the 2D Apollonius diagram, for a given predicate, perturbing a single object (among the objects involved in the predicate evaluation) always suffices, whereas in its 3D counterpart, we may need to perturb two input objects (among the objects involved in the predicate evaluation).

For a predicate expressed as the sign of a polynomial, the arithmetic degree of a predicate is the minimal degree of a polynomial (or of a combination of a constant number of polynomials) that allows to answer the predicate; the degree of the polynomial is a rough measure of the precision needed to evaluate the predicate exactly and of the error introduced by floating point computation [START_REF] Boissonnat | Efficient algorithms for line and curve segment intersection using restricted predicates[END_REF][START_REF] Devillers | Algebraic methods and arithmetic filtering for exact predicates on circle arcs[END_REF][START_REF] Liotta | Robust proximity queries: An illustration of degree-driven algorithm design[END_REF]. Standard algebraic symbolic perturbation schemes [START_REF] Edelsbrunner | Simulation of simplicity: A technique to cope with degenerate cases in geometric algorithms[END_REF][START_REF] Emiris | A general approach to removing degeneracies[END_REF][START_REF] Seidel | The nature and meaning of perturbations in geometric computing[END_REF] automatically provide the auxiliary predicates that need to be evaluated. The corresponding auxiliary polynomials are, by design, of at most the same algebraic degree as the original polynomial, but evaluating their sign in an efficient manner (e.g., by factorizing) is far from being an obvious task. QSP schemes cannot guarantee that the auxiliary polynomials are of lower algebraic degree than the original one; however, in principle, the auxiliary predicates that we have to deal with are expected to be more tractable, since their analysis is based on geometric considerations.

As for any symbolic perturbation scheme, QSP assumes exact arithmetic to detect degeneracies. For many applications, degeneracies are rare enough to allow for high efficiency using the exact geometric computation paradigm [START_REF] Yap | The exact computation paradigm[END_REF].

In the next section of the paper we formally define the QSP framework. In Section 3 and 4 we describe QSP schemes for the main predicates of two geometric structures: (1) the 2D arrangement of circular arcs and (2) the 2D/3D Apollonius diagram. We end with Section 5, where we discuss the advantages and disadvantages of our framework, and indicate directions for future research.

Let us start with a simple example. Assume that the input is a set of points q 0 , q 1 . . . q n-1 to be sorted by x-coordinates. Degeneracies occur when several points have the same abcissa. A possible perturbation consists in translating point q i horizontally to the right by ε i , for any i, while ensuring that ε 0 ε 1 . . . ε n-1 . Then, when comparing the abcissae of two points with the same abcissa, the one that is considered the rightmost is the one perturbed by the largest translation, which is the one with highest index. If the points are numbered by increasing y-coordinates, then sorting them by perturbed x-coordinates reduces to a lexicographic sorting, which is the usual way of solving equal abcissae degeneracies.

QSP formalizes this approach. The next section formally describes QSP and Section 2.2 illustrates its behavior with simple toy examples.

The QSP scheme

Let G(u) be a geometric structure whose computation depends on a predicate sign(p(u)), where p is a continuous real function. In this formal presentation, p appears as a function of the whole input u; however, in practice, a predicate depends only on a constant size subset of u.

We design the perturbation scheme π as a sequence of successive symbolic perturbations π i (as defined in introduction), 0 ≤ i < N :

π(u, ε) = π 0 (π 1 (π 2 (. . . π N-1 (u, ε N-1 ) . . . , ε 2 ), ε 1 ), ε 0 ), where ε = (ε 0 , ε 1 , ε 2 , . . . , ε N-1 ) ∈ R N ≥0 .
The number of perturbations N is part of the perturbation scheme and usually depends on the input size. Since ε is no longer a single real number, we have to determine how the limit is taken; we thus define G(u) to be the limit:

G(u) = lim ε N-1 →0 + lim ε N-2 →0 + • • • lim ε 1 →0 + lim ε 0 →0 + G(π(u, ε)).
Note that writing the limits in this specific order implies that ε 0 ε 1 . . . ε N -1 . In other words, perturbation π i is bigger than perturbation π i-1 , for i = N -1, . . . , 1.

Each perturbed predicate sign(p(u)) is evaluated as

lim ε N-1 →0 + lim ε N-2 →0 + • • • lim ε 1 →0 + lim ε 0 →0 + sign(p(π(u, ε))). (1)
As for standard symbolic perturbations, the perturbation is effective if this limit always exists and is non-zero.

In this definition, the order of evaluation of the limits is standard, i.e., the limit when ε i goes to 0 is taken before the limit when ε i+1 goes to 0, for i = 0, . . . , N -2. The following theorem states that, under some conditions, it is possible to evaluate the limits in an easier way.

jocg.org

Theorem 1. Let sign(p(u)) be a predicate and let π be a sequence of perturbations as above. We assume the existence of the following limits, for 0

< i ≤ N , i = lim ε N-1 →0 + lim ε N-2 →0 + . . . lim ε N-i →0 + sign(p(π(u, (0, 0, . . . , 0, ε N -i , ε N -i+1 , . . . , ε N-1 )))), i = lim ε N-i →0 +
sign(p(π(u, (0, 0, . . . , 0, ε N -i , 0, . . . , 0)))),

With this notation, the value of the perturbed predicate defined in (1) is N .

If the perturbation is effective, i.e., N = 0, let µ be the smallest index i for which i is non-zero. Then the value of the perturbed predicate is N = µ . Furthermore, if sign(p(π(u, (0, 0, . . . , 0,

ε N -µ , ε N -µ+1 , . . . , ε N-1 )))) does not depend on ε N -µ , ε N -µ+1 , . . . , ε N-1 in a neighborhood of the origin in R µ-1
≥0 , except at the origin, then

N = µ = µ .
The proof of the theorem relies on two lemmas about the limit of the sign of a function of two variables, which formalize two trivial observations. Lemma 2. Let f be a continuous function of two variables (a, b) defined in a neighborhood of the origin. If defined, let lim b→0 + signf (0, b) be denoted as s.

If s = 0 then lim b→0 + lim a→0 + signf (a, b) = s.
Proof. Let us assume that s = 0, i.e., s ∈ {-1, +1}. Then there exists δ > 0 such that ∀b ∈ (0, δ], f (0, b) has constant sign s (thus it does not vanish). Proof. Let s = lim a→0 + signf (a, 0). There exists δ > 0 such that ∀a ∈ (0, δ], signf (a, 0) = s. By the hypothesis in the lemma we have ∀a ∈ (0, δ], ∀b ≥ 0, signf (a, 0) = signf (a, b) = s. The function has constant sign s on ((0, δ] × (0, ∞)) ∩ (U × U ) so the limit is s.

Proof of Theorem 1. Applying Lemma 2 to variables ε N -µ and ε N -µ-1 we get µ = µ+1 and by induction µ = µ+1 = µ+2 = . . . = N .

Applying Lemma 3 µ times to variables ε N -µ and ε N -i for all i < µ yields µ = µ under the hypothesis.

jocg.org

The strategy of evaluation of the perturbed predicate is the following. We first compute p(π(u, (0, 0, . . . , 0))) = p(u); if non-zero, its sign is the result for the predicate, i.e., the value of the perturbed predicate is the value of the non-perturbed predicate in non-degenerate configurations.

If p(u) = 0, we look at the function p(π(u, (0, 0, . . . , ε N-1 ))) = p(π N-1 (u, ε N-1 )); if this function is not vanishing when ε N-1 lies in a sufficiently small neighborhood to the right of 0, its sign can be returned. In other words, the biggest perturbation π N -1 removes the degeneracy; in such a case, smaller perturbations have no influence on the result. More formally, we compute the limit

1 = lim ε N-1 →0 + sign(p(π N-1 (u, ε N-1 ))). ( 2
)
If 1 is non-zero, using Theorem 1, it is returned as the value of the predicate sign(p(u)).

Otherwise, we have to further perturb our geometric input; we examine the limit

2 = lim ε N-1 →0 + lim ε N-2 →0 + sign(p(π N-2 (π N-1 (u, ε N-1 ), ε N-2 ))). (3)
If 2 = 0, then the two biggest perturbations π N -1 and π N -2 actually remove the degeneracy and smaller perturbations are useless. The expression in Eq. ( 3) can be simplified in cases that actually often occur in applications: if

p(π N-1 (u, ε N-1 ))) is zero on [0, η), it is often because the sign of p(π N-2 (π N-1 (u, ε N-1 ), ε N-2 )) does not depend on ε N-1 in [0, η).
In such a case, and provided that this function is also non-zero, we can evaluate its sign using the second part of Theorem 1: by taking ε N-1 = 0, Eq. (3) boils down to

2 = 2 = lim ε N-2 →0 + sign(p(π N-2 (u, ε N-2 ))). ( 4
)
The process is iterated until a non-zero limit is found. To assert that the perturbation scheme π is effective, we need to prove that one of these limits, µ , is indeed non-zero.

When the predicate is a polynomial, we get a sequence of successive evaluations as in algebraic symbolic perturbations; however, the expressions that need to be evaluated have been obtained in a different way and are a priori different. The main advantage of this approach is that we may use a very simple perturbation π ν , since we do not need each perturbation π ν to be effective, but rather the composed perturbation π. For geometric problems, the simplicity of π ν allows us to look at the limit in a geometric manner, instead of algebraically computing some appropriate coefficient of p(π(u, ε)).

Toy examples

We illustrate these principles with four toy examples. Rather than focusing on one or more geometric structures to be computed, we concentrate on the evaluation of a few predicates using QSP. The examples illustrate how the formal QSP framework, presented in the previous section, arrives at resolving the predicates considered in each example. The formal evaluation yields, as expected, exactly the same result to which we would have arrived at via straightforward geometric arguments.

In all examples, we set u = (q, q ) = ((x 0 , x 1 ), (x 2 , x 3 )), a pair of two 2D points and π i (u, ε i ) = u + ε i e i , where e 0 = ((1, 0), (0, 0)), e 1 = ((0, 1), (0, 0)), e 2 = ((0, 0), (1, 0)), and e 3 = ((0, 0), (0, 1)) form the canonical basis of (R 2 ) 2 . The differences between the examples below lie in the evaluated predicate sign(p(u)) and the degenerate position u 0 .

Geometrically, we perturb the input points by first moving their y-coordinates in the positive y-direction, and then their x-coordinates in the positive x-direction. Point q is considered to be perturbed more than point q. In all examples, the degeneracy is resolved by considering only the perturbed point q . In some examples perturbing q along the yaxis suffices to resolve the degeneracy, whereas in others both coordinates of q need to be perturbed to achieve predicate resolution.

As already mentioned, below we perform an algebraic analysis for each predicate to illustrate the principles of our approach. Notice, however, that the predicate's result for each degenerate configuration is immediate if we consider the perturbations geometrically.

First example: orientation of a at triangle

Let p(u) = x 0 x 3 -x 1 x 2 and u 0 = (q, q ) = ((1, 1), (2, 2)). QSP defines the result for sign(p(u 0 )), the orientation of Oqq , as

q * q q O sign(p(u 0 )) = lim ε 3 →0 + lim ε 2 →0 + lim ε 1 →0 + lim ε 0 →0 + sign((1 + ε 0 )(2 + ε 3 ) -(2 + ε 1 )(1 + ε 2 )).
A standard evaluation of this expression would consist in taking the limits in order: sign(p(u 0 )) = lim

ε 3 →0 + lim ε 2 →0 + lim ε 1 →0 + sign((2 + ε 3 ) -(2 + ε 1 )(1 + ε 2 )) = lim ε 3 →0 + lim ε 2 →0 + sign((2 + ε 3 ) -2(1 + ε 2 )) = lim ε 3 →0 + sign(ε 3 ) = 1.
Following the QSP evaluation strategy instead, in such a case, the biggest perturbation, i.e., the perturbation on x 3 , allows us to quickly conclude. The only computed limit is the one in Eq. ( 2):

1 = lim ε 3 →0 + sign(p((1, 1), (2, 2 + ε 3 ))) = lim ε 3 →0 + sign((2 + ε 3 ) -2) = lim ε 3 →0 + sign(ε 3 ) = 1.
The geometric interpretation is that we get the orientation of a triangle Oqq * for a point q * slightly above q .

Second example: orientation of a vertical at triangle

Let p(u) = x 0 x 3 -x 1 x 2 and u 0 = (q, q ) = ((0, 1), (0, 2)). QSP defines the result for sign(p(u 0 )), the orientation of Oqq , as

q * q q O sign(p(u 0 )) = lim ε 3 →0 + lim ε 2 →0 + lim ε 1 →0 + lim ε 0 →0 + sign((0 + ε 0 )(2 + ε 3 ) -(1 + ε 1 )(0 + ε 2 )).

jocg.org

Taking the limits in order leads to:

sign(p(u 0 )) = lim ε 3 →0 + lim ε 2 →0 + lim ε 1 →0 + sign(-(1 + ε 1 )ε 2 ) = lim ε 3 →0 + lim ε 2 →0 + sign(-ε 2 )) = lim ε 3 →0 + sign(-1) = -1.
In this case, the QSP evaluation strategy is to first compute

1 = lim ε 3 →0 + sign(p((0, 1), (0, 2 + ε 3 ))) = lim ε 3 →0 + 0 = 0,
which does not allow us to resolve the degeneracy. Then we observe that sign(p((0, 1), (x 2 , x 3 ))) = sign(-x 2 )

does not depend on x 3 , thus we can evaluate 2 using Eq. ( 4):

2 = lim ε 2 →0 + sign(p((0, 1), (ε 2 , 2))) = lim ε 2 →0 + sign(-ε 2 ) = -1.
Two perturbations π 3 and π 2 must be used, but the simplified evaluation of 2 suffices.

The geometric interpretation is that we look at the orientation of a triangle Oqq * for a moved point q * . Since moving q * slightly above q doesn't change anything to the degeneracy, the point is moved to the right, which resolves the degeneracy.

Third example: points and quadratic form

Let p(u) = x 0 (x 1 -1) -x 2 0 -x 2 (x 3 -1) + x 2 2
and u 0 = (q, q ) = ((0, 2), (0, 1)).

The predicate p stands for the difference of a degenerate quadratic form evaluated at q and q . QSP defines the result for sign(p(u 0 )) as

q * q q O - + + - sign(p(u 0 )) = lim ε 3 →0 + lim ε 2 →0 + lim ε 1 →0 + lim ε 0 →0 + sign Ä ε 0 (2 + ε 1 -1) -ε 2 0 -ε 2 (1 + ε 3 -1) + ε 2 2 ä ,
which could be evaluated as follows:

sign(p(u 0 )) = lim

ε 3 →0 + lim ε 2 →0 + lim ε 1 →0 + sign Ä -ε 2 ε 3 + ε 2 2 ä = lim ε 3 →0 + lim ε 2 →0 + sign (ε 2 (ε 2 -ε 3 )) = lim ε 3 →0 + sign(-ε 3 ) = -1.
Again the evaluation strategy first computes

1 = lim ε 3 →0 + sign(p((0, 2), (0, 1 + ε 3 ))) = lim ε 3 →0 + 0 = 0,
which does not allow us to resolve the degeneracy.

jocg.org

Then we observe that sign(p((0, 2), (x 2 , x 3 ))) = sign(x 2 (x 3 -1)+x 2 2 ) actually depends on x 3 , thus we must evaluate 2 using Eq. ( 3):

2 = lim ε 3 →0 + lim ε 2 →0 + sign(p((0, 2), (ε 2 , 1 + ε 3 ))) = lim ε 3 →0 + lim ε 2 →0 + sign (ε 2 (ε 2 -ε 3 )) = lim ε 3 →0 + sign(-ε 3 ) = -1.
Notice that since sign(p((2, 0), (x 2 , x 3 ))) depends on x 3 , the simplified evaluation of Eq. ( 4) would have given a wrong result:

2 = lim ε 2 →0 + sign(p((2, 0), (ε 2 , 1))) = lim ε 2 →0 + sign(ε 2 2 ) = 1.
The geometric interpretation is that q and q are both on one of the two lines defined by the quadratic equation x(y -1) -x 2 = 0. Point q is first slightly moved upwards but this motion leaves it on that same line, then it is moved to the right, and the sign of the quadratic form depends on the vertical position of q with respect to the other line.

Fourth example: side of a sinusoid

Let p(u) = (x 1 -sin x 0 )(x 3 -sin x 2 ) and u 0 = (q, q ) = ((3, 0), (0, 0)). QSP works even if the predicate is non-polynomial. This predicate is positive if q and q are on the same side of the sinusoid. QSP defines the result for sign(p(u 0 )) as

q * q q - + sign(p(u 0 )) = lim ε 3 →0 + lim ε 2 →0 + lim ε 1 →0 + lim ε 0 →0 + sign(((ε 1 -sin(3 + ε 0 ))(ε 3 -sin ε 2 )) = lim ε 3 →0 + lim ε 2 →0 + lim ε 1 →0 + sign((ε 1 -sin 3)(ε 3 -sin ε 2 )) = lim ε 3 →0 + lim ε 2 →0 + sign(-(sin 3)(ε 3 -sin ε 2 )) = lim ε 3 →0 + sign(-(sin 3)ε 3 ) = -1
In this case, the QSP evaluation strategy first computes

1 = lim ε 3 →0 + sign(p((3, 0), (0, ε 3 ))) = sign(-(sin 3)ε 3 ) = -1
and it allows us to resolve the degeneracy.

The geometric interpretation is that q * is moved slightly above q , so on the side of the sinusoid opposite to q.

Discussion

Multiple epsilons

The idea of utilizing multiple perturbation parameters is already present in Yap's scheme [START_REF] Yap | A geometric consistency theorem for a symbolic perturbation scheme[END_REF], or very recently in Irving and Green's work [START_REF] Irving | A deterministic pseudorandom perturbation scheme for arbitrary polynomial predicates[END_REF], but without the direct geometric interpretation allowed by QSP. In other previous works, such as SoS [START_REF] Edelsbrunner | Simulation of simplicity: A technique to cope with degenerate cases in geometric algorithms[END_REF], the jocg.org algebraic symbolic perturbation framework was proved to be effective by a careful choice of the exponents for ε, depending on the choice of G(u), so as to make some terms negligible. QSP fits in such a traditional framework with a single epsilon, when taking variables ε ν dependent on a single parameter κ that plays the traditional role of ε. For polynomial predicates, it is enough to take ε ν exponentially increasing with respect to ν. For example one such choice can be to set ε N-1 = κ, and

ε ν = Ä exp Ä 1 ε ν+1 ää -1 , for 0 ≤ ν < N -1.
The interest of QSP, however, is not to use this view, but rather have the variables ε ν decoupled; this allows for additional flexibility, and, in particular, permits us to think of the sequence of perturbations in geometric terms.

Eciency The aim of a perturbation scheme is to solve degeneracies, and a common assumption is that such degeneracies are rare enough so that some extra time can be spent to make a reliable decision when a degeneracy happens. Another implicit assumption is that degeneracies are actually detected, that is, it is implicitly assumed that the original predicates are computed exactly, possibly with some filtering mechanism to ensure efficiency [START_REF] Yap | The exact computation paradigm[END_REF].

Nevertheless, the actual additional complexity in case of degeneracy must be addressed. Since QSP is geometrically defined and addresses very general problems, such a complexity analysis cannot be done at the general level. For the two applications described in this paper, the extra predicates needed to resolve the degeneracy have the same complexity as the original ones, while the number of epsilons used to perturb is not bigger than two.

QSP, as many other perturbation schemes, relies on an indexing of the input. However, as mentioned earlier, a given predicate usually depends on a constant number of input objects. It is important to keep in mind that the comparison of indices is necessary only for the few objects involved in a given predicate; sorting the whole input with respect to indices is not required. Generality In the first three toy examples above, after re-indexing the coordinates x i , i = 0, 1, 2, 3, SoS would have taken ε 0 = ε 8 , ε 1 = ε 4 , ε 2 = ε 2 , and ε 3 = ε, which yields the same result as QSP. When it leads to a simple result, the classical algebraic view is a very good solution. However, if the original predicate is a bit intricate, the algebraic way will produce numerous extra predicates to resolve degeneracies. Moreover, as for any predicate, some custom work is often still needed on the polynomial to evaluate it efficiently, e.g., finding a good factorization.

QSP provides a very general approach that is able to handle various predicates, even non-polynomial as in the fourth example. Of course applying this scheme to a given problem requires some problem-specific work, but, as noted in the previous paragraph, this is also often the case for the above-mentioned algebraic approaches. In algebraic approaches, obtaining the coefficient of ε i in a suitable way for an efficient evaluation is a non-trivial task; the task is even harder when the predicate does not boil down to evaluating a single polynomial, as it is the case for Apollonius predicates, which we present in the sequel.

We would not advise the use of QSP for simple cases such as Delaunay triangulations of points where other approaches work well [START_REF] Devillers | Perturbations for Delaunay and weighted Delaunay 3D triangulations[END_REF], but rather only in cases where the predicates jocg.org are very complex or non-polynomial. The applications below use high degree polynomials and QSP is a good solution. As far as we know, no other perturbation scheme has ever been proposed for Apollonius diagrams. Regarding intersections of circles, we successfully addressed the predicate comparing the abscissas of intersection of circles, using QSP in Section 3. The only other result that we know of for perturbing this predicate was recently obtained by Irving and Green [START_REF] Irving | A deterministic pseudorandom perturbation scheme for arbitrary polynomial predicates[END_REF]; it uses a pseudo-random scheme.

Meaningfulness According to a classification by Seidel [START_REF] Seidel | Perturbations in geometric computing[END_REF], a perturbation is geometrically meaningful if it allows some control on the direction (in input data space) used to move away from the degeneracies. As QSP combines simple perturbations, it is easier to make it geometrically meaningful as compared to devising an intricate perturbation that must solve a wide range of degeneracy types. For example, for the Apollonius diagram we will design our QSP perturbation to minimize the number of Apollonius vertices (it is also possible to choose to maximize it). QSP is not independent of indexing, but if this indexing is geometrically meaningful, then we can ensure invariance with respect to some geometric transformations.

Predicates for circular arcs arrangements

To address the problem of computing arrangements of circular arcs by sweep-line algorithms, two necessary predicates have to compare the abscissae of two endpoints of circular arcs and to decide whether one endpoint of a circular arc lies above or below another circular arc. In this section, we address the x-comparison predicate, which was studied in a previous paper [START_REF] Devillers | Algebraic methods and arithmetic filtering for exact predicates on circle arcs[END_REF]. The other predicate is simpler and we leave as an exercise for the reader to check that the proposed perturbation also resolves its degeneracies.

The arc endpoints are described as intersections of two circles, which leads us to consider the arrangement of all circles supporting arcs or defining their endpoints. Degeneracies occur if several vertices of the arrangement have the same abscissa or if more than two circles meet at a common point. For arrangements exhibiting a lot of degeneracies, it may be interesting to design an algorithm that directly handles special cases, while in other contexts where degeneracies are occasional, it would be preferable to keep the algorithm simple and handle degeneracies through a perturbation scheme.

In the formalism of the previous section, u is a vector of parameters defining a set of circular arcs and G(u) is the arrangement. Let us introduce more specific notations for this application. An endpoint z ν,µ , defined as an intersection of two circles C ν and C µ , is determined by the centers (α ν , β ν ) and (α µ , β µ ) of the circles (see Figure 1), their squared radii γ ν and γ µ , and a Boolean b ν,µ encoding whether z ν,µ is the leftmost l ν,µ or rightmost intersection point r ν,µ (if they have the same abscissa, r ν,µ is the highest and l ν,µ the lowest intersection point).

Journal of Computational Geometry jocg.org

(α i , β i ) √ γ i p i , j x + q i , j y + s i , j = 0 L i,j r i,j L k,m r k,m C i C j C k C m Figure 1:
x-comparison of endpoints: a degenerate case where r i,j and l k,m have the same abcissa.

Algebraic formulation

Let us introduce the line L ν,µ , whose equation p ν,µ x + q ν,µ y + s ν,µ = 0 is obtained by subtracting the equations of C ν and C µ . We observe that the intersection points of C ν and C µ can also be seen as intersections between C ν and L ν,µ . The coefficient of L ν,µ are:

p ν,µ = 2(α ν -α µ ), q ν,µ = 2(β ν -β µ ), and s ν,µ = γ ν -γ µ -α 2 ν -β 2 ν + α 2 µ + β 2 µ . The predicate x-compare(C i , C j , b i,j , C k , C m , b k,m
) compares the abscissae of two arc endpoints z i,j defined by C i , C j , and b i,j (i = j) on the one hand, and z k,m defined by C k , C m , and b k,m (k = m) on the other hand. The most complicated evaluation is the sign of the following degree 12 polynomial [START_REF] Devillers | Algebraic methods and arithmetic filtering for exact predicates on circle arcs[END_REF]:

(A i,j C k,m -A k,m C i,j ) 2 -4(A i,j B k,m -A k,m B i,j )(B i,j C k,m -B k,m C i,j )
where:

A ν,µ = p 2 ν,µ + q 2 ν,µ , B ν,µ = q 2 ν,µ α ν -p ν,µ ( s ν,µ + q ν,µ β ν ), C ν,µ = (s ν,µ + q ν,µ β ν ) 2 + q 2 ν,µ (α 2 ν -γ ν ).
Introducing an algebraic symbolic perturbation yields quite a complicated polynomial in ε, not really suitable for efficient predicate evaluation. For the same problem, Irving and Green [START_REF] Irving | A deterministic pseudorandom perturbation scheme for arbitrary polynomial predicates[END_REF] use an algebraic perturbation with pseudo-random coefficients, but they only address the special case where C i = C k .

Qualitative symbolic perturbation

We construct a sequence of N = n + 1 successive perturbations for an input C consisting of n circles C ν , 0 ≤ ν < n.

jocg.org The first perturbation, π n (C, ε n ) is a rotation centered at the origin and with angle ε n . This perturbation handles the cases where z i,j and z k,m are different points with the same abscissa. Actually if z i,j = z k,m , with the notations of Theorem 1, 1 = 0 and the sign of the perturbed predicate is the one of 1 . In other words, it just uses lexicographic comparisons: y-comparisons are used to break ties in x-comparisons (see Figure 2(a)). The rotation by a small angle has the same effect as a shear transform. A shear transform is often preferred in the literature because it is a rational transformation. We use a rotation instead because it transforms circles into circles, which is preferable in order to apply the remaining perturbations in the sequence. On top of that, we are not interested in the algebraic formulation of the transformation, since we look at the limit in a geometric way instead of algebraically.

(a) z i,j left of z k,m C i C j C m C k ε n z i,j z k,m (b) z i,j right of z k,m (e) z i,j right of z i,m (d) z i,j left of z i,m z ε k,m z ε i,j C i = C k C j C m ε i z i,j = z k,m z ε i,j z ε i,m ε i C i = C k C j C m z i,j = z k,m z ε i,j z ε i,m C i C j C m C k ε i z ε i,j z i,j = z k,m z i,j = z k,m C i C j C m C k ε i z ε i,j ε n (c) z i,j left of z k,m z ε k,m
In fact, the next perturbations alone may remove the degenerate x-comparisons, but the main interest of adding this first perturbation is to treat these degeneracies in a meaningful way.

We are now left with cases when z i,j = z k,m . The other perturbations in the sequence consist in inflating the circles:

π ν (C, ε ν ) replaces γ ν by γ ε ν = γ ν + ε ν , ε ν ≥ 0.
Recall that the comparison of indices is necessary only for the four circular arcs involved in a given jocg.org predicate; sorting the whole input with respect to indices is not required. We consider the circles by decreasing radii to get rid of pairs of tangent circles in a geometrically meaningful way: if two circles are tangent, the perturbation inflates the largest one by a larger amount, making the intersection point either disappear if the two circles are internally tangent, or split into two points if they are externally tangent.

Without loss of generality, we may assume that i ≥ j, k, m, i.e., C i is the most perturbed circle. If i ∈ {k, m}, then z i,j moves (i.e., z ε i,j = z i,j ) while z k,m stays fixed. If C i and C j have a non-vertical tangent in z i,j and after determining the vertical order of C i and C j at the right of z i,j , and whether z i,j is on the top or bottom part of C i using the auxiliary predicates described below, it is easy to decide if z ε i,j moves left or right when ε i > 0 (see Figure 2(b)). With the notations of Theorem 1, 1 = 0 since z i,j = z k,m , 2 , . . . , N -i-1 = 0 since the corresponding perturbations do not affect a circle involved in the current predicate and N -i is the first non-zero value in the ( µ ) sequence. Furthermore, the side z ε i,j is not dependent from the initial rotation nor the unperturbed circles, thus N -i = N -i .

If C i or C j have a vertical tangent in z i,j , then we have to consider the rotation to find the sign of the perturbed slope before determining the side of z ε i,j (see Figure 2(c)). With respect to Theorem 1, N -i is still the first non-zero value in the sequence ( µ ) but

N -i can be different from N -i . If i ∈ {k, m}, assume, without loss of generality, that i = k. If z ε i,j and z ε i,m
are perturbed in opposite x-directions, it is easy to decide which one is the leftmost (see Figure 2(d)). Otherwise, we determine the vertical order of the three circles C i , C j , and C m at the right of z i,j = z i,m ; we know that C i is either the topmost or the bottommost circle in this vertical ordering. The point lying on the closest arc to C i is more perturbed than the other, and the auxiliary predicates below allow us to decide which of z ε i,j and z ε i,m is to the left (see Figure 2(e)). As in the previous case, Theorem 1 applies and N -i is the first non-zero value, and N -i = N -i if there is no vertical tangent in z i,j .

Auxiliary predicates A circle can be split in four parts: top-right, top-left, bottom-left, and bottom-right at its points with horizontal or vertical tangents. Knowing if a point z i,j is on the left or right part of C i can be evaluated by x-compare

(C i , C j , b i,j , C i , C m , b i,m ) for a suitable C m such that L i,m has equation x -α i = 0.
Discriminating between the top and bottom parts is done in the same way, by exchanging the roles of the x-and y-coordinates. Another predicate consists in deciding if C i is above or below C j at the right of r i,j ; this can be done by elementary geometric computations.

The Apollonius diagram

In this section, we describe how QSP applies to predicates related to the Apollonius diagram in dimensions 2 and 3.

jocg.org

Figure 3: Planar Apollonius diagram. Weighted points are in light blue. A green disk is centered at an Apollonius vertex and its radius is the weighted distance of the center to its three closest sites. The darker green disk has a negative distance to its closest neighbors.

Denition

The Apollonius diagram, also known as additively weighted Voronoi diagram, is defined on a set of weighted points in the Euclidean space R d . In the formalism of Section 2, u is a vector of coordinates and weights of a set of weighted points and G(u) is the Apollonius diagram; as in Section 3, we introduce additional specific notations. The Euclidean norm is denoted as | • |. The weighted distance from a query point q to a weighted point (p, w), where p is a point in the Euclidean space and w ∈ R, is |pq| -w. The Apollonius diagram is the closest point diagram for this distance. It generalizes the Voronoi diagram, defined on non-weighted points.

Given a set of weighted points, also called sites, adding the same constant to all weights does not change the Apollonius diagram. Thus, in the sequel, we may freely translate the weights to ensure, for example, that all weights are positive, or that a particular weight is zero. A site (s, w), w ≥ 0, can be identified with the sphere S centered at s and of radius w. The distance from a query point r to a site S = (s, w) is the Euclidean distance from r to S, with a negative sign if r lies inside S.

An Apollonius vertex v is a point at the same distance from d + 1 sites S 0 , S 1 , . . . , S d in general position. We call the configuration external if v is outside sphere S i , for all i = 0, . . . , d, and internal if it is inside the spheres. If the configuration is external (resp., internal), v is the center of a sphere externally (resp., internally) tangent to the sites S i (see green (resp., dark green) disks in Figure 3). It is always possible to ensure an external configuration locally by adding a suitable constant to the weights of all S i , such that all weights are non-negative, while the smallest among them is equal to zero. Let us show that d + 1 sites in general position define 0, 1 or 2 Apollonius vertices. Assume, without loss of generality, that all weights are non-negative for i = 1, . . . , d and w 0 = 0, so as to have an external configuration. Consider now the inversion with point s 0 as the pole. The point s 0 goes to infinity, while each sphere S i , i = 1, . . . , d becomes a new sphere Z i = (z i , ρ i ) (see Figure 4). Determining the balls B α (where α indexes the different solutions) tangent to the spheres S i , i = 0, . . . , d is equivalent to determining halfspaces delimited by the hyperplanes T α tangent to the spheres Z i , i = 1, . . . , d, with all spheres on the same side of T α . that a given B α is externally tangent to the spheres S i is equivalent to requiring that T α separates the spheres Z i from the origin. The normalized equation of T α : λ α • x + δ α = 0, with λ α ∈ R d ,|λ α | = 1 and δ α ∈ R, gives the signed distance of a point x ∈ R d to T α . We have

T α tangent to Z i , 1 ≤ i ≤ d ⇐⇒ ® λ α • z i + δ α = ρ i , 1 ≤ i ≤ d |λ α | 2 = 1 . (5)
In the inverted space, the general position hypothesis means that the spheres Z i do not have an infinity of tangent hyperplanes; the latter can occur only if the points z i (and thus the points s i ) are affinely dependent. Therefore, the system (5) of one quadratic and d linear equations in d + 1 unknowns (λ α ∈ R d and δ α ∈ R) has at most two real solutions by Bézout's theorem, hence the first claim follows. Depending on the position of the origin with respect to T α (or equivalently on the sign of δ α ), zero, one or both solutions may correspond to external configurations.

An Apollonius vertex is actually defined by a sequence of d + 1 sites in general position, up to a positive permutation of the sequence. Indeed, in the previous paragraph, if there are two solutions T α and T α , we observe that they are symmetric with respect to the hyperplane spanned by the points z i , thus the d-simplex formed by the tangency points and the origin has different orientations for the two solutions (see Figure 5). This implies that the two solutions can be distinguished by the signature of the permutation of the spheres S i .

jocg.org

S i0 B v Q - "conflict" "degenerate" "no conflict" t i0 t i 1 S i1 t i 2 S i2 Q Q Q Q Q - Q - Q - Figure 6:
Examples of positions of Q or Q -that are in "conflict", "degenerate" or "no conflict" configuration with an Apollonius vertex v.

The VConflict predicate

We start with the vertex conflict predicate VConflict(S v , Q), which answers the following question:

Does an Apollonius vertex v defined, up to a positive permutation, by a (d + 1)tuple of sites S v = (S i 0 , S i 1 , . . . , S i d ) remain as a vertex of the diagram after another site Q is added?

This predicate is intrinsic to computing an Apollonius diagram: it boils down to computing the diagram of the d + 2 sites, thus any algorithm able to compute the diagram of these sites allows to answer the predicate. If the site centered at v and tangent to the sites of the tuple S v is in internal configuration, we can add a negative constant to the radii of all spheres in S v ∪ {Q} so that the smallest site in S v has zero radius. Then the configuration of the common tangent sphere becomes external. In this manner, we can always restrict our analysis to the case where the Apollonius vertex we consider is in external configuration. Note that this may lead to a negative weight w q for Q, which was a priori excluded above, but is treated below.

We denote by B i 0 i 1 ...i d the open ball whose closure B i 0 i 1 ...i d is tangent to the sites of S v ; its boundary is denoted ∂B i 0 i 1 ...i d . The contact points t i 0 , t i 1 , . . . , t i d define a positively oriented d-simplex.

If w q ≥ 0, the predicate VConflict(S v , Q) answers (Figure 6)

Journal of Computational Geometry jocg.org • "conflict" if Q intersects B i 0 i 1 ...i d , • "no conflict" if Q and B i 0 i 1 ...i d are disjoint, • "degenerate" if Q and B i 0 i 1 ...i d do not intersect, while Q and B i 0 i 1 ...i d are tangent.
If w q < 0, we define Q -as the sphere with the same center s q as Q and radius -w q . Then VConflict(S v , Q) answers Qualitative perturbation of the VConflict predicate QSP relies on some ordering of the sites. Each site S ν = (s ν , w ν ) is perturbed to S ε ν = (s ν , w ν + ε ν ), ε ν ≥ 0, with S λ perturbed more than S ν if λ > ν. Following the QSP framework, if the configuration is still degenerate after we have enlarged the site of maximum index, then we enlarge the site with the second largest index, and so on. As mentioned in the general presentation (Section 2.3), we need only consider the sites involved in the predicate, and enlarge them one-by-one until the resulting configuration is non-degenerate, in which case the predicate is resolved. Sites are sorted internally in the predicate, among a constant number of objects; there is no need for any global sorting of the sites.

• "conflict" if Q -is included in B i 0 i 1 ...i d , • "no conflict" if Q -intersects the complement of B i 0 i 1 ...i d , • "degenerate" if Q -is included in B i 0 i 1 ...
Any indexing can be used. We choose what we call the max-weight indexing, which assigns a larger index to the site with larger weight. As a result, a site with larger weight is perturbed more, and in order to resolve the predicate we need to consider the sites in order of decreasing weights, until the degeneracy is resolved. To break ties between sites with the same weights, we use the lexicographic comparison of their centers: among two sites with the same weight, the site whose center is lexicographically smaller than the other is assigned a smaller max-weight index. The max-weight indexing has the strong advantage of being geometrically meaningful. It favors sites with larger weights, so, if two sites are internally tangent, then the site with the larger weight will be perturbed more, in which case the site with the smallest weight will be inside the interior of the other site, and its Apollonius region will disappear in the perturbed diagram. As a first consequence, this indexing minimizes the number of Apollonius regions in the diagram, or, equivalently it maximizes the number of hidden sites in the diagram. Secondly, and most importantly, the tangency points of the sites with the Apollonius circles that they define in the diagram are pairwise distinct. This property makes the analysis of the perturbed predicates much simpler, whereas the Apollonius diagram computed does not exhibit pathological cases, such as Apollonius regions with empty interiors. Some inevitable degenerate constructions, such as zero-length Apollonius edges, are handled seamlessly by the method. As a final comment, the max-weight scheme can be used to resolve the degeneracies of all predicates described by Emiris and Karavelas for the 2D case [START_REF] Ioannis | The predicates of the Apollonius diagram: algorithmic analysis and implementation[END_REF].

Perturbing circles for the 2D Apollonius diagram

In two dimensions, the two main predicates for computing Apollonius diagrams are the VConflict predicate introduced in the previous section and the EConflict predicate, which will be analyzed in Section 4.3.5. Other predicates deal with special cases such as infinite Apollonius edges and can be treated in a similar manner.

Algebraic expression for the 2D VConflict predicate

Let S i , S j , S k be the three sites that define an Apollonius circle in the Apollonius diagram and let Q = S q be the query site.

Let us first define some intermediate quantities:

x * ν = x ν -x i , y * ν = y ν -y i , w * ν = w ν -w i , p * ν = (x * ν ) 2 + (y * ν ) 2 -(w * ν ) 2 , ν ∈ {j, k, q}, E s = s * j p * j s * k p * k , E st = s * j t * j p * j s * k t * k p * k s * q t * q p * q ,
s, t ∈ {x, y, w},

and ∆ = (E x ) 2 + (E y ) 2 -(E w ) 2 .
In the algebraic formulation of the predicate by Emiris and Karavelas [START_REF] Ioannis | The predicates of the Apollonius diagram: algorithmic analysis and implementation[END_REF], the evaluation of VConflict(S i , S j , S k , Q) relies on the computation of the sign of the expression I:

I := E xw E x + E yw E y + E xy √ ∆.
The expression I is of the form X 0 + X 1 √ Y , where the algebraic degrees of X 0 , X 1 and Y are 7, 4 and 6, respectively. Its sign can be computed by means of the formula sign

(X 0 + X 1 √ Y ) =              sign(X 1 ) if X 0 = 0 sign(X 0 ) if X 1 = 0 or Y = 0 sign(X 0 ) if sign(X 0 ) = sign(X 1 ) sign(X 0 ) sign(X 2 0 -X 2 1 Y ) otherwise. ( 6
)
It is thus concluded by Emiris and Karavelas that the algebraic degree of the predicate is 14 [START_REF] Ioannis | The predicates of the Apollonius diagram: algorithmic analysis and implementation[END_REF]Theorem 11].

In fact we can further decrease the algebraic degree of the predicate by observing that the quantity X 2 0 -X 2 1 Y can be factorized as follows (see [START_REF] Devillers | Qualitative Symbolic Perturbation: a new geometry-based perturbation framework[END_REF]Appendix B] for the details of this derivation):

X 2 0 -X 2 1 Y = [(E x ) 2 + (E y ) 2 ] [(E xw ) 2 + (E yw ) 2 -(E xy ) 2 ],
where the first factor is a non-negative quantity of degree 6, whereas the second factor is of degree 8. In fact, when we compute the sign of the quantity X 2 0 -X 2 1 Y , we already know that the quantity (E x ) 2 + (E y ) 2 is strictly positive, since otherwise X 0 would have been zero (X 0 is a linear combination of E x and E y ), which has already been ruled out according to the procedure in Eq. ( 6). Hence the algebraic degree of the predicate is 8. Before using our qualitative symbolic perturbation framework to design the perturbed predicate, we briefly sketch how a standard algebraic perturbation framework could be applied.

Algebraic perturbation of the 2D VConflict predicate

If S ν = (x ν , y ν , w ν ) is perturbed in S ε ν = (x ν , y ν , w ν + ε ν ) for ν ∈ {i, j, k, q}, then developing an expression like (E xw ) 2 will give a polynomial of degree 6 in ε i , ε j , ε k and ε q with 186 terms. Assigning ε i , ε j , ε k and ε q to be polynomial functions of a single variable ε (for example, we may set ε ν = ε αν , ν ∈ {i, j, k, q}) transforms the expression to a univariate polynomial in ε. When performing such an assignment, either some of the terms collapse making their geometric and algebraic interpretation difficult, or α i , α j , α k and α q have to be chosen carefully so that the coefficients of the various monomials of the variables ε ν in the resulting polynomial do not collapse. Even if one could find an assignment that does not make the coefficients (of the originally different terms) collapse, we are still faced with the problem of analyzing the monomials, and, by employing algebraic and/or geometric arguments, showing that there is at least one coefficient of the polynomial that does not vanish.

Qualitative perturbation of the 2D VConflict predicate

We now precisely describe how the perturbation works on the VConflict predicate in dimension 2. What follows in this section does not depend on the actual algebraic formulation of the VConflict predicate; instead our entire analysis is based on purely geometric arguments.

Let us denote by q the max-weight index of Q, i.e., Q = S q . We denote with superscript ε the perturbed version of objects, that is B ε ijk is a shorthand for the ball tangent to S ε i , S ε j , and S ε k , and

VConflict ε (S i , S j , S k , S q ) = lim

ε i 3 →0 + lim ε i 2 →0 + lim ε i 1 →0 + lim ε i 0 →0 + VConflict(S ε i , S ε j , S ε k , Q ε ) with i 0 < i 1 < i 2 < i 3 , {i 0 , i 1 , i 2 , i 3 } = {i, j, k, q}.
If q > i, j, k and VConflict (S i , S j , S k , Q) = "degenerate", we compute the limit given by Eq. ( 2)

1 = lim εq→0 + VConflict(S i , S j , S k , Q ε ).
It is clear that this limit always evaluates to "conflict", since Q is growing while the open ball B ijk whose closure is tangent to S i , S j , and S k can be considered as fixed. Thus we can apply Theorem 1 and we do not need to look at perturbations of smaller indices (see Figure 7). If q is not the largest index, then B ijk can be viewed as defined by three other circles among S i , S j , S k , and Q. Since B ijk = B jki = B kij , we can assume, without loss of generality, that i > j, k, q. Moreover, B ijk coincides with either B jkq or B kjq , depending on the orientation of the tangency points of S j , S k and Q with B ijk .

In the perturbed setting, S ε i is in conflict with B ε jkq (or B ε kjq ) since S ε i is growing, while B ε jkq can be considered as fixed. We simply need to determine if B ε ijk remains empty in the perturbed setting. Let t ν (resp., t q ) be the tangency point of S ν (resp., Q) with B ijk , jocg.org

B ijk Q perturb "conflict" B ijk v v ε Q ε "conflict" B ijk dual-view
is no longer an Apollonius vertex v ε Figure 7: Perturbing a degenerate Apollonius vertex: the case q > i, j, k. ν ∈ {i, j, k}, and notice that t i t j t k is a ccw triangle. We consider three cases depending on the position of t q on ∂B ijk . If t q is different from t i , t j , and t k , the four points form a convex quadrilateral. When perturbing S i to become S ε i , the Apollonius vertex is split in two, which, in the dual,1 corresponds to a triangulation of the quadrilateral with vertices S i , S j , S k , S q . Since S i is the most perturbed circle, the quadrilateral will be triangulated by linking S i to the other three vertices. If t q is on the same side as t i with respect to the line t j t k , then the triangulation contains triangle S i S j S k and, therefore, Q is not in conflict with B ijk (see Figure 8), otherwise S i S j S k is not in the triangulation and Q has to be in conflict with B ijk (see Figure 9). If t q is equal to t i then, since i > q, the site Q is internally tangent to S i and there is no conflict (S ε i contains Q in its interior, and thus Q has empty Apollonius region in the diagram). If t q is equal to t ν with ν ∈ {j, k} then either Q is internally tangent to S ν , or S ν is internally tangent to Q. In the former case, Q does not intersect the perturbed Apollonius disk B ε ijk and thus the result of the perturbed predicate is "no conflict"; in the latter case, Q intersects B ε ijk , and the perturbed predicate returns "conflict". Hence, in the case t q = t ν , ν ∈ {j, k}, the perturbed predicate returns "conflict" if an only if q > ν.

jocg.org

α = π α < π α > π v ijk S i t i t j t k S j S k s j s k Q c s q Q n t q tj t k v ijk S i t i t j t k S j S k s j s k Q c Q c Q n tj t k v ijk S i t i t j t k S j S k s j s k Q c Q n Q n tj t k s q t q s q t q s q t q s q t q s q t q s q t q s q t q Figure 10:
Computing the auxiliary predicate Orientation(t j , t k , t q ) using orientations involving the Apollonius vertex v ijk . From left to right: the case α = π, the case α > π, and the case α < π, where α is the angle of the ccw oriented arc tj t k .

(resp., Q c ) in Figure 10(left) to illustrate a position of Q not in conflict (resp., in conflict)). o 1 = "ccw". In this case α > π. We start by evaluating o 2 = Orientation(s j , v ijk , s q ). If o 2 = "ccw" (see Q c in Figure 10(middle)), t q lies to the right of the line through t j and t k , and thus Orientation(t j , t k , t q ) = "cw". Otherwise, we need to evaluate the orientation o 3 = Orientation(v ijk , s k , s q ); then Orientation(t j , t k , t q ) = "ccw" if and only if o 3 = "ccw" (see Q n and Q c in Figure 10(middle)). o 1 = "cw". In this case α < π. We start by evaluating o 2 = Orientation(s j , v ijk , s q ). If o 2 = "cw", t q lies to the left of the line through t j and t k , and thus Orientation(t j , t k , t q ) = "ccw" (see Q n in Figure 10(right)). Otherwise, we need to evaluate the orientation o 3 = Orientation(v ijk , s k , s q ); then Orientation(t j , t k , t q ) = "cw" if and only if o 3 = "cw" (see Q c and Q n in Figure 10(right)).

To summarize, the evaluation of Step 7 requires at most three orientation tests involving an Apollonius vertex and two sites; one may be obtained as a subproduct of Step 1, while the other two require work similar to the work performed for Step 1. Thus, the evaluation of Step 7 does not increase the algebraic degree of the VConflict predicate.

Qualitative perturbation for the 2D EConflict predicate

The computation of the 2D Apollonius diagram requires another predicate. When a new site is added it is not enough to find which Apollonius vertices remain or disappear: we need a more complete analysis of the modification of the edges of the diagram. This is the subject of the EConflict predicate. Given four sites S i , S j , S k and S l that define a Voronoi edge e in the diagram, and a query site Q, EConflict determines the type of conflict of Q with the edge e. This predicate boils down to computing the diagram of the 5 sites, thus any algorithm able to compute the diagram of these sites allows to answer the predicate. This predicate is the basis of the randomized incremental construction algorithm for computing abstract Voronoi diagrams by Klein, Mehlhorn, and Meiser [START_REF] Klein | Randomized incremental construction of abstract Voronoi diagrams[END_REF], as well as one of the main predicates analyzed by Emiris and Karavelas [START_REF] Ioannis | The predicates of the Apollonius diagram: algorithmic analysis and implementation[END_REF]. In [START_REF] Ioannis | The predicates of the Apollonius diagram: algorithmic analysis and implementation[END_REF] this predicate is decomposed to a number of subpredicates, one of them being the VConflict predicate.

We assume below that e lies on the bisector of S i and S j , oriented so that S i is lying to the right of the bisector (refer also to Figure 11). The edge e inherits the orientation from its supporting bisector. The origin vertex of e is the Apollonius vertex defined by the (oriented) triple S i , S j and S k , while the target vertex of e is the Apollonius vertex defined by the triple S j , S i and S l . The EConflict predicate determines the type of the subset of e that is destroyed by the insertion of Q in the Apollonius diagram of the four sites, and has six possible outcomes:

• "conflict origin": a subsegment of e adjacent to its origin vertex disappears in the Apollonius diagram of the five sites. This case occurs if and only if VConflict ε (S i , S j , S k , Q) = "conflict" and VConflict ε (S j , S i , S l , Q) = "no conflict". This case is illustrated by Q cn in Figure 11.

• "conflict target": is the symmetric case that occurs iff VConflict ε (S i , S j , S k , Q) = "no conflict" and VConflict ε (S j , S i , S l , Q) = "conflict". See Q nc in Figure 11.

• "no conflict": no portion of e is destroyed by the insertion of Q in the Apollonius diagram of the four sites. This case can occur only when VConflict ε (S i , S j , S k , Q) = VConflict ε (S j , S i , S l , Q) = "no conflict". See Q nn in Figure 11.

• "conflict interior": a subsegment in the interior of e disappears in the Apollonius diagram of the five sites. This case can occur only when VConflict ε (S i , S j , S k , Q) = VConflict ε (S j , S i , S l , Q) = "no conflict". See Q nn in Figure 11.

• "conflict entire edge":

the entire edge e is destroyed by the addition of Q in the Apollonius diagram of the four sites. This case can occur only when VConflict ε (S i , S j , S k , Q) = VConflict ε (S j , S i , S l , Q) = "conflict". See Q cc in Figure 11.

• "conflict both": subsegments of e adjacent to its two vertices disappear in the Apollonius diagram of the five sites. This case can occur only when VConflict ε (S i , S j , S k , Q) = VConflict ε (S j , S i , S l , Q) = "conflict". See Q cc in Figure 11.

Thus when the evaluations of predicate VConflict ε on (S i , S j , S k , Q) and (S j , S i , S l , Q) are available, it only remains to distinguish between "no conflict" and "conflict interior", as well as between "conflict entire edge" and "conflict both". Assuming a non-degenerate configuration, this question is addressed in [START_REF] Ioannis | The predicates of the Apollonius diagram: algorithmic analysis and implementation[END_REF] using an auxiliary predicate of algebraic degree 16. The only situation where this auxiliary predicate has degeneracies is when VConflict(S i , S j , S k , Q) or VConflict(S j , S i , S l , Q) are "degenerate" and VConflict ε (S i , S j , S k , Q) = VConflict ε (S j , S i , S l , Q). Then the predicate can be answered by looking at the relative position of t q with respect to t i and t j on ∂B ijk (or the relative position of t q with respect to t i and t j on ∂B jil ). More precisely EConflict ε (S i , S j , S k , S l , Q) can be evaluated by means of the following procedure. Figure 12 describes the different degeneracies that may occur.

S j S i S k S l Q cc Q cc Q nn Q nn Q cn Q nc B ijk B jil
1. if (VConflict ε (S i , S j , S k , Q) = "conflict"
and VConflict ε (S j , S i , S l , Q) = "no conflict") then return "conflict origin";

2. if (VConflict ε (S i , S j , S k , Q) = "no conflict" solving VConflict degeneracies. An Apollonius vertex v ijkl is defined by four sites S i , S j , S k , and S l , while the predicate VConflict(S i , S j , S k , S l , Q) tests if after adding a fifth site Q = S q , vertex v ijkl remains a valid Apollonius vertex or not. Let B ijkl denote the open ball tangent to S i , S j , S k , and S l , whose tangency points t i , t j , t k , and t l form a positively oriented tetrahedron t i t j t k t l .

The predicate in general position can be solved in different ways. One way is to do like Boissonnat and Delage [START_REF] Boissonnat | Convex hull and Voronoi diagram of additively weighted points[END_REF]. Another way is to use inversion like in the 2D case by Emiris and Karavelas [START_REF] Ioannis | The predicates of the Apollonius diagram: algorithmic analysis and implementation[END_REF], and arrive at an alternative expression [START_REF] Marinov | The Euclidean InSphere Predicate[END_REF][START_REF] Kamarianakis | [END_REF]. In degenerate configuration, Q and B ijkl are tangent at t q and we can obtain, as a side product, the orientations of the tetrahedra formed by 4 of the 5 tangency points t i , t j , t k , t l , and t q .

As for the 2D case, we apply the max-weight QSP scheme. If the predicate is degenerate the effect of the perturbation is that the weight of the site with largest weight increases and thus this site intersects the ball tangent to the four other sites. In the neighborhood of the center of B ijkl the Apollonius diagram of S i , S j , S k , S l , and Q has the same combinatorial structure as the Voronoi diagram of t i , t j , t k , t l , and t q . We, thus, get an equivalent formulation for the predicate: given five co-spherical points t i , t j , t k , t l , and t q , does the tetrahedron t i t j t k t l remain in the Delaunay triangulation when the point of the largest index is moved inside the ball. Notice that it implies that the point with largest index is linked to all other points in this Delaunay triangulation.

Similarly to the two-dimensional case, we can conclude that Q is in conflict with B ijkl if q > i, j, k, l. We can also take care of the cases where t q is equal to one of the four points t i , t j , t k , and t l . Otherwise, we rename the indices so that i is the largest one. The definition of B ijkl says that tetrahedron t i t j t k t l is positively oriented. Notice that this can be true in two ways: either the tetrahedron is really positively oriented, or it is flat, as the limit of a positively oriented tetrahedron when ε i → 0 + . If t q t j t k t l is positively oriented, t q and t i are on the same side of t j t k t l , which is a facet of the convex hull of the five points. Since the 3D Apollonius graph is "star-shaped" from S i , S i is linked to S j S k S l to create the tetrahedron S i S j S k S l , and thus there is no conflict for Q.

If t q t j t k t l is negatively oriented, t q and t i are on opposite sides of t j t k t l , which implies that S j S k S l ceases to be a facet of the Apollonius graph. Thus, the tetrahedron S i S j S k S l disappears and Q is in conflict.

If t q t j t k t l is flat, the question reduces to determining the orientation of t ε q t ε j t ε k t ε l , which are the points of tangency of S q , S j , S k , S l with B ε ijkl after the perturbation of S i by ε i . This orientation will be non-degenerate except in two very special cases where the centers of Q, S j , S k , and S l are either co-circular or collinear.

We first address the case where s q , s j , s k , and s l are neither co-circular nor collinear. Let us assume that l is smaller than j and k, which means that w l ≤ w j , w k . By subtracting w l from all weights, we can consider that S l has zero weight, and then perform an inversion with pole s l (see Figure 13). Let Z i , Z j , Z k , and Z q be the images of sites S i , S j , S k , and Q, and ω i , ω j , ω k , and ω q be the images of t i , t j , t k , and t q under inversion, and denote by z i , z j , z k , and z q the centers of Z i , Z j , Z k , and Z q . Since t q t j t k t l is a flat tetrahedron, jocg.org

inversion: pole s l t j t k Z q Z j Z k S j S k t i t l = s l Q t q ω k ω j ω i Z i ω q Z q Z j Z k Z ε i S i perturb S i B ijkl T ijk T ijk T ε ijk ω k ω j ω ε i "conflict"
Figure 13: The case, for the VConflict predicate, where the tetrahedron t q t j t k t l is flat.

the four points t q , t j , t k , t l are co-circular and thus ω q , ω j , ω k are collinear. Their supporting line lies in the plane T ijk , image of B ijkl under inversion, and which contains ω i , ω j , and ω k . The plane T ijk is the unique plane commonly tangent to all three sites Z q , Z j , and Z k . The uniqueness follows from the fact that z q , z j , and z k are not collinear, since s q , s j , s k , and s l = t l have been assumed to be neither co-circular nor collinear. Let C denote the cone with axis z j z k , whose generatrices are common tangents to Z j and Z k , and whose apex lies outside the segment z j z k . Any plane tangent to both Z j and Z k and having Z j and Z k on the same side is also tangent to C. When we perturb S i to S ε i , the plane T ijk moves a bit, in the set of planes tangent to C, to become T ε ijk . Consider first the case w q ≥ w l , which implies that the weight of Z q is non-negative. Since z q , z j , and z k are not collinear and Z q is tangent to C at ω q , the sphere Z q either properly intersects C or is inside C. If Z q is (tangent to and) inside C, then, for all values of ε i , the plane T ε ijk does not intersect Z q , and the result of the perturbed predicate is "no conflict", otherwise, for all values of ε i , the plane T ε ijk intersects Z q , and the result of the perturbed predicate is "conflict". The way to evaluate the VConflict ε predicate, in this case, is by determining the value of the orientation of z j z k z q in the plane that is perpendicular to T ijk and passes through z j and z k , oriented such that z j z k ω j is positive. If w j = w k = w l , the cone C degenerates to the line through z j and z k . In this case we have w q > w l (since, otherwise, s j , s k , s l and s q would have been co-circular), and thus VConflict ε returns jocg.org 13. if t j t k t l and t q t k t l have the same 2D orientation then return "no conflict"; else return "conflict";

Steps 8 and 9 of the above algorithm rely on the auxiliary predicate Orientation(t q , t j , t k , t l ) that, given five sites, computes the orientation of the four tangency points on the common tangent sphere to the fifth site. Since the tetrahedron t i t j t k t l is, by definition positively oriented, Orientation(t q , t j , t k , t l ) will be positive if and only if t q lies on the same half of B ijkl as t i , where the two halves of B ijkl are delimited by the circle through t j , t k and t l . We first reduce all the weights by w l . If w j = w k = w l (= 0), computing the orientation of t q , t j , t k , t l amounts to evaluating the orientation of t q , s j , s k , s l . If w j , w k and w l are not all equal, we consider again the inversion transformation with s l as the pole. Then t q lies on the same half of B ijkl as t i if and only if ω q lies on the same half-plane of T ijk , with respect to the line through ω j and ω k , as ω i . The equality of these 2D orientation tests is equivalent to testing the result of Orientation(z q , z j , z k , ω ); if Orientation(z q , z j , z k , ω ) = "ccw" return "no conflict", otherwise return "conflict".

For Step 10 we first need to test if the points s j , s k , s l and s q are either collinear or co-circular. The possible collinearity can easily be tested via the cross-products (s l -s j ) × (s k -s j ) and (s q -s j ) × (s k -s j ); if both are the zero vector, the four points are collinear. Co-circularity in the original space corresponds to collinearity in the inverted space (where the pole of inversion is s l ); to test if s j , s k , s l and s q are co-circular it suffices to test if z j , z k , z q are collinear, which amounts to computing the cross-product (z q -z j ) × (z k -z j ). The 2D orientations of z q , z j , z k and ω , z j , z k are evaluated by determining, for a point x ∈ plane(z q z j z k ), if the two tetrahedra z q z j z k x and ω z j z k x have the same orientation.

Finally, if the centers s j , s k , s l , s q are co-circular the 2D orientations of t j t k t l and t q t k t l in Step 13 are the same as those of s j s k s l and s q s k s l . Choosing a point x ∈ plane(s j s k s l ), we may compute these 2D orientations via their 3D counterparts s j s k s l x and s q s k s l x. If the centers s j , s k , s l , s q are collinear, notice that, due to the fact that the tetrahedron t i t j t k t l is positively oriented, s k lies inside the segment s j s l . Hence, determining if the 2D orientations of t j t k t l and t q t k t l are the same reduces to determining if s q lies inside the segment s k s l or not; in the former case we return "conflict", while in the latter case we return "no conflict". We end this section by briefly discussing the algebraic degree of three-dimensional VConflict ε predicate. The unperturbed predicate can be evaluated with algebraic expressions of degree at most 10 [13]; this accounts for Step 1 of the algorithm described above. Steps 2, 3, 11 and 12 all amount to comparing indices of sites, so they are all of degree 1. To resolve Steps 4 to 7 we need to test whether the points of tangency of two spheres with the common Voronoi sphere coincide; this amounts to testing whether one sphere is internally tangent to another one, which is a degree-2 predicate. Step 13 can easily be resolved using expressions of degree at most 6 [START_REF] Kamarianakis | [END_REF], while Steps 10(i) and 10(ii) are clearly degree-1 operations. The most demanding parts of our evaluation procedure are Steps 8, 9 and 10(iii). Their algebraic degrees can be shown to be 28 and 20, respectively [START_REF] Kamarianakis | [END_REF]. Hence, the VConflict ε predicate can be evaluated, as described above, with expressions of algebraic degree at most 28.

Journal of Computational Geometry jocg.org

Conclusion

In this paper, a new framework for dealing with geometric degeneracies has been proposed: QSP. Conversely to usual approaches for symbolic perturbation, the new framework does not rely on a particular algebraic description of the predicate, but rather directly on its geometric description.

A QSP scheme consists of a sequence of perturbations, but given a specific predicate only a few of these perturbations are really active. The number of active perturbations used to resolve a specific predicate depends on the problem at hand. For the 2D Apollonius diagram perturbing one site always suffices. In its 3D counterpart we may need to perturb two sites, whereas in the case of circular arcs we may need perform a rotation (perturb the axes) and perturb up to one supporting circle per predicate. Minimizing the number of active perturbations is not necessarily desirable, since it might result in a more complicated design for the perturbed predicate (for example, trying to resolve degeneracies for the trapezoidal map of circular arcs with a single active perturbation seems much more complicated).

Besides the number of active perturbations, another important issue is the ordering of the perturbations: for the Apollonius diagram we consider sites by decreasing weight, whereas for the arrangement of circular arcs we first consider a (global) rotation and then the circles by means of decreasing radius. Different perturbation sequences than the ones described in this paper are definitely possible; the analysis, however, can become unnecessarily more complicated.

Our qualitative symbolic perturbation framework, and in particular the schemes described in this paper, can also be applied to a variety of other problems, such as the 2D Voronoi diagram of disjoint convex objects under any L p metric, as well as the Euclidean Voronoi diagram of certain disjoint convex objects in 3D (the objects can be, for example, non-intersecting lines, line segments or rays). It suffices to replace a site S i by its Minkowski sum with a ball of radius ε i , and then consider the limits ε i → 0 + , for an appropriately defined ordering of the sites. Another type of geometric problem, involving complex predicates, for which the QSP framework is relevant, is the computation of lines tangent to four given lines in 3D [START_REF] Brönnimann | Lines and free line segments tangent to arbitrary three-dimensional convex polyhedra[END_REF][START_REF] Devillers | Predicates for line transversals to lines and line segments in three-dimensional space[END_REF].

Lemma 3 .

 3 For any b fixed in (0, δ] the function f (a, b) is a continuous function in variable a, thus lim a→0 + f (a, b) = f (0, b). Since f (0, b) = 0, the sign of f (a, b) is the same as the sign of f (0, b) when a is in a neighborhood of 0, so lim a→0 + signf (a, b) = signf (0, b) = s. Thus lim b→0 + lim a→0 + signf (a, b) = lim b→0 + s = s. The function f (a, b) = a shows that the hypothesis s = 0 is necessary. Let f be a continuous function in two variables (a, b) defined in a neighborhood U × U of the origin. Assume that ∀a ∈ U, ∀b, b ∈ U with a > 0 and b, b ≥ 0 we have signf (a, b) = signf (a, b ) and lim a→0 + signf (a, 0) exists. Then lim

Figure 2 :

 2 Figure 2: Perturbing z i,j and z k,m

Figure 4 :

 4 Figure4: The spheres B α externally tangent to the sites S i , i = 0, . . . , d, correspond, via the inversion transformation with s 0 as the pole, to hyperplanes T α tangent to the spheres Z i that separate them from the origin.

Figure 5 :

 5 Figure 5: If T α and T α are both external, the simplices formed by the tangency points and the origin have different orientations.

  i d and is tangent to its boundary.

Figure 11 :

 11 Figure 11: The different non-degenerate possible configurations for the EConflict predicate.

Figure 12 :

 12 Figure 12: The different degenerate possible configurations for the EConflict predicate.

The dual of the Apollonius diagram is called Apollonius graph. The Apollonius region of a site Si is associated to a vertex of the dual graph, thus Si can be used to refer to the corresponding vertex in the dual graph.

Acknowledgments The authors warmly thank the reviewers for their very careful reading of the paper and their detailed comments and suggestions.

* The work in this paper has been partially supported by the FP7-REGPOT-2009-1 project "Archimedes Center for Modeling, Analysis and Computation". M. Karavelas acknowledges support by the European Union (European Social Fund -ESF) and Greek national funds through the Operational Program "Education and Lifelong Learning" of the National Strategic Reference Framework (NSRF) -Research Funding Program: THALIS -UOA (MIS 375891). -Grand Est, France.

.

dual-view remains an Apollonius vertex v ε the case i > j, k, q and t j t k t q is a ccw triangle.

Practical evaluation of the 2D VConflict ε predicate

Following the analysis in the previous section, VConflict ε (S i , S j , S k , Q) can be evaluated by the following procedure:

1. if VConflict(S i , S j , S k , Q) = "degenerate" then return VConflict(S i , S j , S k , Q); 2. if q > max{i, j, k} then return "conflict"; 3. ensure that i > max{j, k} by a cyclic permutation of (i, j, k); 4. if t q = t i then return "no conflict"; 5. if t q = t j then { if q > j then return "conflict"; else return "no conflict"; }; 6. if t q = t k then { if q > k then return "conflict"; else return "no conflict"; }; 7. if t j t k t q is ccw then return "no conflict"; else return "conflict";

Step 1 is evaluated as described in Section 4.3.1. Steps 2 and 3 amount to sorting the indices (i.e., the weights) of the four sites and determining if q is the largest, or, if this is not the case, finding the largest index. At Step 4, we already know that i > q, which implies that w i ≥ w q , and hence the only possibility is that Q is internally tangent to S i . So, in order to perform Step 4, we simply look at p * q = (x q -x i ) 2 + (y q -y i ) 2 -(w q -w i ) 2 : if p * q = 0, return "no conflict", otherwise continue with Step 5. Steps 5 and 6 can be resolved in a similar way: if (x q -x ν ) 2 + (y q -y ν ) 2 -(w q -w ν ) 2 = 0, then if q > ν (resp., q < ν), we return "conflict" (resp., "no conflict"). Otherwise, we continue with the last step of the procedure. the case i > j, k, q and t j t k t q is a cw triangle.

We will now focus on this last step, Step 7, because it introduces a new geometric predicate, which is difficult to evaluate: Orientation(t j , t k , t q ), for three tangency points. Our aim is to reduce the complexity of the expressions to be evaluated, which is why we avoid computing the tangency points explicitly. The end of this section describes a method with algebraic degree 8, as in Step 1. This computation can be done in another way: in [8, Appendix A] we proposed an alternative method that requires very few additional arithmetic computations besides the quantities already computed in the unperturbed evaluation of Step 1, however these few extra computations have algebraic degree 12.

It has been shown in [START_REF] Ioannis | The predicates of the Apollonius diagram: algorithmic analysis and implementation[END_REF] that evaluating the orientation of three points where two are centers of sites and the third is an Apollonius vertex, can be performed using algebraic expressions of degree at most 14. In fact, this degree may be decreased to 8 (see [8, Appendix B]), in which case we resolve Orientation(t j , t k , t q ), without resorting to a higher degree predicate, as described below.

Firstly, we evaluate o 1 = Orientation(s j , v ijk , s k ), where v ijk is the center of the Apollonius circles B ijk of the three sites S i , S j , S k . We perform this evaluation in order to determine whether the angle α of the ccw arc tj t k on B ijk is more or less than π. Secondly, we distinguish between the following cases (see Figure 10): o 1 = "collinear". In this case α = π, and the line through t j and t k coincides with the line through s j and s k . Hence: Orientation(t j , t k , t q ) = Orientation(s j , s k , s q ) (see Q n and VConflict ε (S j , S i , S l , Q) = "conflict") then return "conflict target";

and VConflict(S i , S j , S k , Q) = "degenerate") then return EConflict(S i , S j , S k , S l , Q); 12] else return "conflict interior"; [Q dn in Figure 12] else [in this case: VConflict(S j , S i , S l , Q) = "degenerate"] if t j t i t q is ccw then return "no conflict"; else return "conflict interior"; 12] else return "conflict entire edge"; [Q dc in Figure 12] else [in this case: VConflict(S j , S i , S l , Q) = "degenerate"] if t j t i t q is ccw then return "conflict both"; else return"conflict entire edge";

The main observation from the above pseudocode is that the max-weight qualitative perturbation scheme described in Section 4.2 not only resolves the VConflict predicate, but also the EConflict predicate (although not described in this paper, our perturbation scheme resolves, in fact, all degeneracies of all predicates used in [START_REF] Ioannis | The predicates of the Apollonius diagram: algorithmic analysis and implementation[END_REF] for the computation of the 2D Apollonius diagram). To resolve the EConflict predicate, we need only evaluate Orientation(t i , t j , t q ) or Orientation(t j , t i , t q ).

As described in the previous section, this predicate is of algebraic degree 8, and thus does not increase the algebraic degree of the EConflict predicate. Furthermore, with a careful implementation, it is possible to keep track of the intermediate results of the evaluation of the VConflict ε predicate and resolve the EConflict predicate using these intermediate results in a purely combinatorial manner.

As a final note, the above procedure for the evaluation of the EConflict predicate works as is even when the Apollonius edge e is of zero length. This is the case when the Apollonius vertices v ijk and v jil coincide, or, equivalently, when the four sites S i , S l , S j and S k are all tangent (and in that ccw order) to the same Apollonius circle. The only difference with respect to the non-zero-length Apollonius edge case are the possible outcomes: the EConflict predicate will never return "conflict interior" nor "conflict both"; this is, however, automatically handled by the procedure described above, that is without the need to handle any additional special cases.

Perturbing spheres for the 3D Apollonius diagram

In dimension three the most critical predicate is the VConflict predicate. Solving degeneracies for other predicates such as EConflict or FConflict boils down, as in dimension two, to jocg.org "conflict". If at least two of w j , w k , w l differ, then at least one of ω j and ω k differs from z j and z k , respectively. Denoting by ω a point of tangency that differs from the corresponding center, it suffices to determine if Orientation(z q , z j , z k ) = Orientation(ω , z j , z k ), in which case the VConflict ε predicate returns "no conflict", otherwise "conflict" is returned.

Finally, notice that when w q < w l , the site Z q has negative weight. In this case, the sphere Z - q will properly intersect the plane T ε ijk for all values of ε i , which implies that S q does not intersect B ε ijk . Hence, in this case, the result of the perturbed predicate is "no conflict". In all cases above, perturbing S i is sufficient to remove the degeneracy. In the very degenerate cases where s j , s k , s l , and s q are co-circular or collinear, the unique edge of the (degenerate) Apollonius diagram of S j , S k , S l , and Q is a circle or a line. In these cases, the position of S i has no influence on the combinatorial structure of the diagram of S i , S j , S k , S l , and Q, and we need to perturb the second most perturbed site S j or S k or Q to remove the degeneracy. The resolution of the degeneracy is similar to the 2D case: first perform a positive permutation of j, k, l to ensure that j > k, l. If q > j then Q will be in conflict, otherwise, if q < j then Q will be in conflict if and only if t j t k t l and t q t k t l have different two-dimensional orientations.

Following the above analysis, VConflict ε (S i , S j , S k , S l , Q) can be evaluated as follows:

1. if VConflict(S i , S j , S k , S l , Q) = "degenerate" then return VConflict(S i , S j , S k , S l , Q); 2. if q > max{i, j, k, l} then return "conflict"; 3. ensure that i > max{j, k} ≥ min{j, k} > l by a positive permutation of (i, j, k, l); 4. if t q = t i then return "no conflict"; 5. if t q = t j then { if q > j then return "conflict"; else return "no conflict"; }; 6. if t q = t k then { if q > k then return "conflict"; else return "no conflict"; }; 7. if t q = t l then { if q > l then return "conflict"; else return "no conflict"; }; 8. if t q t j t k t l is positively oriented then return "no conflict"; 9. if t q t j t k t l is negatively oriented then return "conflict"; 10. if s j , s k , s l , s q are neither collinear nor co-circular then i. if w q < w l then return "no conflict"; ii. if w j = w k = w l then return "conflict";

iii. compute a tangency point ω ;

if z q , z j , z k and ω , z j , z k have the same 2D orientation then return "no conflict"; else return "conflict";

11. ensure that i > j > max{k, l} by a positive permutation of (j, k, l);

12. if q > j then return "conflict";