Hazel Everett
email: hazel.everett@loria.fr

Sylvain Lazard
email: sylvain.lazard@loria.fr

Daniel Lazard
email: daniel.lazard@lip6.fr

Mohab Safey
email: mohab.safey@lip6.fr

El Din

The Voronoi Diagram of Three Lines

Keywords: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems-Geometrical problems and computations, I.1.2 [Symbolic and Algebraic Manipulation]: Algorithms-Algebraic algorithms, I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling -Curve, surface, solid, and object representations Theory, Algorithms Voronoi diagram, medial axis, quadric surface intersection

We give a complete description of the Voronoi diagram of three lines in R 3 . In particular, we show that the topology of the Voronoi diagram is invariant for three lines in general position, that is, that are pairwise skew and not all parallel to a common plane. The trisector consists of four unbounded branches of either a non-singular quartic or of a cubic and line that do not intersect in real space. Each cell of dimension two consists of two connected components on a hyperbolic paraboloid that are bounded, respectively, by three and one of the branches of the trisector. The proof technique, which relies heavily upon modern tools of computer algebra, is of interest in its own right.

This characterization yields some fundamental properties of the Voronoi diagram of three lines. In particular, we present linear semi-algebraic tests for separating the two connected components of each two-dimensional Voronoi cell and for separating the four connected components of the trisector. This enables us to answer queries of the form, given a point, determine in which connected component of which cell it lies. We also show that the arcs of the trisector are monotonic in some direction. These properties imply that points on the trisector of three lines can be sorted along each branch using only linear semi-algebraic tests.

INTRODUCTION

The Voronoi diagram of a set of disjoint objects is a decomposition of space into cells, one cell per object, such that the cell associated with an object consists of all points that are closer to that object than to any other object. In this paper, we consider the Voronoi diagram of lines in R 3 under the Euclidean metric.

Voronoi diagrams have been the subject of a tremendous amount of research. For points, these diagrams and their complexities are well understood and optimal algorithms as well as robust and efficient implementations exist for computing them in any dimension (see for instance [START_REF] Aurenhammer | Voronoi diagrams -a survey of a fundamental geometric data structure[END_REF][START_REF] Aurenhammer | Voronoi diagrams[END_REF][START_REF] Boissonnat | Triangulations in CGAL[END_REF][START_REF] Boissonnat | Applications of random sampling to on-line algorithms in computational geometry[END_REF][START_REF] Chan | Primal dividing and dual pruning: Output-sensitive construction of four dimensional polytopes and three-dimensional diagram voronoi diagrams[END_REF][START_REF] Clarkson | Applications of random sampling in computational geometry[END_REF][START_REF] Fortune | Voronoi diagrams and delaunay triangulations[END_REF][START_REF] Okabe | Spatial Tessellations -Concepts and Applications of Voronoi Diagrams[END_REF][START_REF] Pion | 3d triangulations[END_REF][START_REF] Seidel | A convex hull algorithm optimal for point sets in even dimensions[END_REF]). Nevertheless, some important problems remain and are addressed in recent papers. The same is true for segments and polygons in two dimensions [START_REF] Karavelas | A robust and efficient implementation for the segment voronoi diagram[END_REF].

For lines, segments, and polyhedra in three dimensions much less is known. In particular, determining the combinatorial complexity of the Voronoi diagram of n lines or line segments in R 3 is an outstanding open problem. The best known lower bound is Ω(n 2 ) and the best upper bound is O(n 3+ε ) [START_REF] Sharir | Almost tight upper bounds for lower envelopes in higher dimensions[END_REF]. It is conjectured that the complexity of such diagrams is near-quadratic. In the restricted case of a set of n lines with a fixed number, c, of possible orientations, Koltun and Sharir have shown an upper bound of O(n 2+ε ), for any ε > 0 [START_REF] Koltun | Three dimensional euclidean voronoi diagrams of lines with a fixed number of orientations[END_REF].

There are few algorithms for computing exactly the Voronoi diagram of linear objects. Most of this work has been done in the context of computing the medial axis of a polyhedron, i.e., the Voronoi diagram of the faces of the polyhedron [START_REF] Culver | Computing the Medial Axis of a Polyhedron Reliably and Efficiently[END_REF][START_REF] Milenkovic | Robust construction of the voronoi diagram of a polyhedron[END_REF]. Recently, some progress has been made on the related problem of computing arrangements of quadrics (each cell of the Voronoi diagram is a cell of such an arrangement) [START_REF] Berberich | An exact, complete and efficient implementation for computing planar maps of quadric intersection curves[END_REF][START_REF] Keyser | Efficient and accurate B-Rep generation of low degree sculptured solids using exact arithmetic: I -Representations, II -Computation[END_REF][START_REF] Mourrain | On the computation of an arrangement of quadrics in 3D[END_REF][START_REF] Schömer | An exact and efficient approach for computing a cell in an arrangement of quadrics[END_REF][START_REF] Schwarzkopf | Vertical decomposition of a single cell in a three-dimensional arrangement of surfaces and its applications[END_REF]. Finally, there have been many papers reporting algorithms for computing approximations of the Voronoi diagram (see for instance [START_REF] Dey | Approximate medial axis as a voronoi subcomplex[END_REF][START_REF] Etzion | Computing voronoi skeletons of a 3-d polyhedron by space subdivision[END_REF][START_REF] Hoff | Fast computation of generalized Voronoi diagrams using graphics hardware[END_REF][START_REF] Teichmann | Polygonal approximation of voronoi diagrams of a set of triangles in three dimensions[END_REF]).

In this paper, we address the fundamental problem of understanding the structure of the Voronoi diagram of three lines. A robust and effective implementation of Voronoi diagrams of three-dimensional linear objects requires a complete and thorough treatment of the base cases, that is the diagrams of three and four lines, points or planes. We also strongly believe that this is required in order to make progress on complexity issues, and in particular for proving tight worst-case bounds. We provide here a full and complete characterization of the geometry and topology of the elementary though difficult case of the Voronoi diagram of three lines in general position.

Main results. Our main result, which settles a conjecture of Koltun and Sharir [START_REF] Koltun | Three dimensional euclidean voronoi diagrams of lines with a fixed number of orientations[END_REF], is the following (see Figure 1). THEOREM 1. The topology of the Voronoi diagram of three pairwise skew lines that are not all parallel to a common plane is invariant. The trisector consists of four infinite branches of either a non-singular quartic 1 or of a cubic and a line that do not intersect in P 3 (R). Each cell of dimension two consists of two connected components on a hyperbolic paraboloid that are bounded, respectively, by three and one of the branches of the trisector.

The proof technique, which relies heavily upon modern tools of computer algebra, is of interest in its own right. We also provide a geometric characterization of the configurations of three lines (which are pairwise skew and not all parallel to a common plane) whose trisector is not generic, that is consists of a cubic and a line.

The characterization of Theorem 1 yields some fundamental properties of the Voronoi diagram of three lines which are likely to be critical for the analysis of the complexity and the development of efficient algorithms for computing Voronoi diagrams and medial axes of lines or polyhedra. In particular, we obtain the following results. MONOTONICITY PROPERTY. Given three pairwise skew lines that are not all parallel to a common plane, there is a direction in which all four branches of the trisector are monotonic. THEOREM 2. Let p be a point that lies in (i) a two-dimensional cell or (ii) the one-dimensional cell of the Voronoi diagram of three pairwise skew lines that are not all parallel to a common plane. There are linear semi-algebraic tests for (i) deciding on which connected components of the twodimensional cell, point p lies, or (ii) deciding on which branches of the trisector, point p lies, respectively.

Furthermore, if the three lines are rational, these linear tests are rational. 2 Moreover, there is a linear semi-algebraic test for (iii) ordering points on each branch of the trisector.

Notice that the tests (i) and (ii) enable us to answer queries of the form, given a point, determine in which connected component of which cell it lies. Notice also that tests (ii) and (iii) should be useful for computing the Voronoi diagram of n lines since it requires to locate the points equidistant to four lines on a Voronoi arc of three of these lines.

The rest of the paper is organized as follows. The next section gives the proof of Theorem 1. In Section 3, we present some fundamental properties of the Voronoi diagram of three lines and algorithms for separating the components of each cell of the diagram. We also prove the Monotonicity Property and Theorem 2. Finally, we give, in Section 4, a geometric characterization of the configurations of three lines in general position such that their trisector contains a line.

PROOF OF THEOREM 1

We consider three lines in general position, that is, that are pairwise skew and not all parallel to the same plane. The idea is to prove that the topology of the trisector is invariant by continuous deformation on the set of all triplets of three lines in general position and that this set is connected. The result then follows from the analysis of any example.

We show that the trisector is always homeomorphic to four lines that do not pairwise intersect. To prove this, we show that the trisector is always non-singular in P 3 (R) and has four simple real points at infinity. To show that the trisector is always non-singular, we study the type of the intersection of two bisectors, which are hyperbolic paraboloids.

Z 2 : y = -ax z = -1 1 : y = ax z = 1 (x, y, 0) (α, β , 1) 3 X
We use the classic result that the intersection of two quadrics is a non-singular quartic (in P 3 (C)) unless the characteristic equation of their pencil has (at least) a multiple root. In order to determine when this equation has a multiple root, we determine when its discriminant ∆ is zero.

This discriminant has several factors, some of which are trivially always positive. The remaining, so-called "gros facteur", can be shown, using Safey's software [START_REF] Rag | Lib: A Library for real algebraic geometry[END_REF], to be never negative. This implies that it is zero only when all its partial derivatives are zero. We thus consider the system that consists of the gros facteur and all its partial derivatives, and compute its Gröbner basis. This gives three equations of degree six. We consider separately two components of solutions, one for which a (simple) polynomial F is zero, the other for which F = 0.

When F = 0, some manipulations and simplifications, which are interesting in their own rights, yield another Gröbner basis, with the same real roots, which consists of three equations of degree four. We show that one of these equations has no real root which implies that the system has no real root and thus that ∆ = 0 has no real root on the considered component. We can thus conclude that, in this case, the trisector is always a non-singular quartic in P 3 (R). When F = 0, we show, by substituting F = 0 in ∆ and by using the classification of the intersection of quadrics over the reals [START_REF] Dupont | Near-optimal parameterization of the intersection of quadrics: II. A classification of pencils[END_REF], that the trisector is a cubic and a line that do not intersect in P 3 (R).

We can thus conclude that the trisector is always a non-singular quartic or a cubic and a line that do not intersect in real space and thus that the trisector is always non-singular in P 3 (R).

We then prove that the trisector always contains four simple real points at infinity and thus that it is always homeomorphic to four lines that do not pairwise intersect. It follows that the topology of the Voronoi diagram is invariant by continuous deformation on any connected set of triplets of lines in general position. Next we prove that the set of triplets of lines in general position is connected which implies that the topology of the Voronoi diagram is constant. We finally determine the topology of (any) one arbitrary triplet of lines, which yields the result.

In the rest of this section, we prove Theorem 1.

Preliminaries

Let 1 , 2 , and 3 be three lines in general position, i.e., that are pairwise skew and not all parallel to a common plane. Refer to Figure 2. Let (X,Y, Z) denote a Cartesian coordinate system. Without loss of generality, we assume that 1 and 2 are both horizontal, pass through (0, 0, 1) and (0, 0, -1) respectively, and have directions that are symmetric with respect to the XZ-plane. More precisely, we assume that line 1 is defined by point p 1 = (0, 0, 1) and vector v 1 = (1, a, 0), and line 2 by point p 2 = (0, 0, -1) and vector v 2 = (1, -a, 0), a ∈ R. Moreover, since the three lines are not all parallel to a common plane, 3 is not parallel to the plane z = 0, and so we can assume that line 3 is defined by point p 3 = (x, y, 0) and vector v 3 = (α, β, 1), x, y, α, β ∈ R.

We denote by H i, j the bisector of lines i and j and by V i j the Voronoi cell of lines i and j , i.e., the set of points equidistant to i and j and closer to them than to k , k = i, j. We recall the following well-known elementary facts. The Voronoi cells are connected and star-shaped [START_REF] Leven | Intersection and proximity problems and voronoi diagrams[END_REF]. The bisector of two pairwise skew lines is a right hyperbolic paraboloid, that is, has equation of the form Z = γ X Y , γ ∈ R, in some coordinate system (see for instance [START_REF] Koltun | Three dimensional euclidean voronoi diagrams of lines with a fixed number of orientations[END_REF]); for completeness we present a proof of this fact. LEMMA 3. The bisector of two pairwise skew lines is a right hyperbolic paraboloid.

PROOF. The bisector of two lines i and j is the set of points p satisfying the equation

(p -p i ) × v i 2 v i 2 = (p -p j ) × v j 2 v j 2 . ( 1
)
Without loss of generality, we prove the lemma for the two lines 1 and 2 . For these lines, the above equation simplifies into the following equation of a right hyperbolic paraboloid:

Z = - a 1 + a 2 X Y.
(2)

Algebraic structure of the trisector, Part I

The trisector of our three lines is the intersection of two right hyperbolic paraboloids, say H 1,2 and H 1,3 . The intersection of two arbitrary hyperbolic paraboloids may be singular; it may be a nodal or cuspidal quartic, two secant conics, a cubic and a line that intersect, a conic and two lines crossing on the conic, etc (see [START_REF] Dupont | Near-optimal parameterization of the intersection of quadrics: II. A classification of pencils[END_REF]Table 4]). We show here that the trisector is always non-singular by studying the characteristic polynomial of the pencil of H 1,2 and H 1,3 .

Let Q 1,2 and Q 1,3 be matrix representations of H 1,2 and H 1,3 ,

i.e. the Hessian of the quadratic form associated with the surface (see, for instance, [START_REF] Dupont | Near-optimal parameterization of the intersection of quadrics: I. The generic algorithm[END_REF]). The pencil of Q 1,2 and Q 1,3 is the set of linear combinations of them, that is,

P(λ) = {λQ 1,2 + Q 1,3 , ∀λ ∈ R}.
The characteristic polynomial of the pencil is the determinant, D(λ) = det(P(λ)), which is a degree four polynomial in λ. The intersection of any two quadrics is a non-singular quartic, in P 3 (C), if and only if the characteristic equation of the corresponding pencil does not have any multiple roots (in C) [START_REF] Segre | Studio sulle quadriche in uno spazio lineare ad un numero qualunque di dimensioni[END_REF] (see also [START_REF] Dupont | Near-optimal parameterization of the intersection of quadrics: II. A classification of pencils[END_REF]). A non-singular quartic of P 3 (C) is, in P 3 (R), either empty or a nonsingular quartic. Thus, since the trisector of our three lines cannot be the empty set in R 3 , the trisector is a smooth quartic in P 3 (R) if and only if the characteristic equation of the pencil does not have any multiple roots (in C).

The characteristic polynomial of the pencil is fairly complicated (roughly one page in the format of Eq. ( 3)). However, by a change of variable λ → 2 λ (1 + α 2 + β 2 ) and by dividing out the positive factor (1 + a 2 ) 2 (1 + α 2 + β 2 ) 3 , the polynomial simplifies, without changing its roots, to the following, which we still denote by D(λ) for simplicity.

D(λ) = α 2 + β 2 + 1 a 2 λ 4 -2 a 2 aβ 2 + ayβ + aα x -β α + 2 a + 2 aα 2 -β α a 2 λ 3 + β 2 + 6 a 2 β 2 -2 β xa 3 -6 β α a 3 + 6 yβ a 2 -6 aβ α -2 aβ x + 6 α xa 2 +y 2 a 2 -2 aα y + x 2 a 2 -2 yα a 3 + 6 a 2 α 2 + a 4 α 2 + 4 a 2 λ 2 -2 xa -ya 2 -2 β a 2 -β + 2 aα + α a 3 (xa -y -β + aα) λ + 1 + a 2 (xa -y -β + aα) 2 (3)
In the sequel, all polynomials are considered over the reals, that is for λ, a, α, β, x, y in R, unless specified otherwise. We start by studying the sign of D(λ). PROOF. We prove that the real semi-algebraic set S = {χ = (λ, a, x, y, α, β) ∈ R 6 | D(χ) < 0} is empty using a development version of the RAGLIB Maple library [START_REF] Rag | Lib: A Library for real algebraic geometry[END_REF] which is based on the algorithm presented in [START_REF] Din | Generalized critical values and testing sign conditions on a polynomial[END_REF]. The algorithm computes at least one point per connected component of such a semi-algebraic set and we observe that, in our case, this set is empty. Before presenting our computation, we first describe the general idea of this algorithm.

Suppose first that S = R 6 and let C denote any connected component of S. We consider here D as a function of all its variables χ = (λ, a, x, y, α, β) ∈ R 6 . The algorithm first computes the set of generalized critical values 3 of D (see [START_REF] Din | Generalized critical values and testing sign conditions on a polynomial[END_REF] for an algorithm computing them). The image by D of C is an interval whose endpoints 4 are zero and either a negative generalized critical value or minus infinity. For any v in this interval, there is a point where v is any value smaller than zero and larger than the largest negative generalized critical value, if any. Finally, a randomly chosen point p in R 6 also needs to be added, if D(p) < 0, to ensure that we find a point in every connected component of S in the case where S = R . Now, computing at least one point in every connected component hypersurface defined by D(χ) = v can be done by computing the points of the distance function between the surface and a say the origin, that is, by solving the system D(χ) = v, χ × grad(D)(χ) = 0. This conceptually simple approach, developed in [START_REF] Rouillier | Finding at least one point in each connected component of a real algebraic set defined by a single equation[END_REF], is, however, not computationally efficient. The efficient algorithm presented in [START_REF] Din | Generalized critical values and testing sign conditions on a polynomial[END_REF] computes instead critical points of projections, combining efficiently the strategies given in [START_REF] El Din | Properness defects of projections and computation of one point in each connected component of a real algebraic set[END_REF] and [START_REF] El Din | Polar varieties and computation of at least one point in each connected component of a smooth real algebraic set[END_REF].

χ 0 ∈ C such that D(χ 0 ) = v,
The result of the computation of at least one point in every connected component of S shows that S empty (see the full paper for details) and thus that D(χ) 0 for all χ ∈ R 6 . It should be noted that these computations are very fast: they take roughly 3 seconds of elapsed time on a standard PC. Let ∆ the discriminant of the characteristic polynomial D(λ) (with respect to λ). Recall that D(λ) admits a multiple root if and only if its discriminant is zero. COROLLARY 5. The discriminant ∆ is never negative. PROOF. By Lemma 4, D(λ) is either always positive or has a multiple root. If a degree-four polynomial is always positive, then it easily follows from the definition that its discriminant is positive [8, §3 p. 119]. Furthermore, if a polynomial has a multiple root then its discriminant is zero. REMARK 6. The proof that ∆ is never negative can also be proved with the RAGLIB library, as in the proof of Lemma 4, but the computation is then a lot more time consuming (roughly 10 hours instead of 3 seconds).

D(χ

The discriminant ∆ of the characteristic polynomial, computed with Maple [START_REF]Waterloo Maple Software[END_REF], is equal to

16 a 4 (a x -y -β + a α) 2 (y + a x -a α -β) 2 (4)
times a factor that we refer to as the gros facteur which is a rather large polynomial of which we only show 2 out of 40 lines:

gros_facteur = 8 a 8 α 4 y 2 + 7 a 4 β 2 x 4 -4 aβ 3 x + 16 a 8 β 4 x 4 + 32 a 4 α 2 y 2 • • • + 22 a 4 y 2 β 2 x 2 + y 6 a 6 + α 2 y 6 a 6 -2 β xα y 5 a 6 + x 6 a 6 + 10 β x 3 a 7 α 2 . ( 5
)
LEMMA 7. The discriminant ∆ is equal to zero if and only if the gros facteur and all its partial derivatives are equal to zero.

PROOF. The polynomial (4) is not equal to zero under our general position assumption. Indeed, a = 0 is equivalent to saying that lines 1 and 2 are parallel and the two other factors of (4) are equal to the square of det(p ip 3 , v i , v 3 ), for i = 1, 2, and thus are equal to zero if and only if i and 3 are coplanar, for = 1, 2. It follows that (4) is always strictly positive. Thus, the discriminant ∆ is equal to zero if and only if the gros facteur is zero. Furthermore, by Corollary 5, the gros facteur is never negative, thus, if there exists a point where the gros facteur vanishes, it is a local minimum of the gros facteur and thus all its partial derivatives (with respect to {a, x, y, α, β}) are zero.

Note that Lemma 7 says, in other words, that the zeros of ∆ are the singular points 5 of the gros facteur.

We now state our main lemma which implies that the discriminant is zero only if a simple condition is satisfied.

MAIN LEMMA. The discriminant ∆ is equal to zero only if y + a α = 0 or a x + β = 0.
PROOF. By Lemma 7, ∆ is zero if and only if the gros facteur and all its partial derivatives are zero. We prove below that this implies that (y + a α)

(a x + β) (1 + α 2 + β 2 ) Γ = 0, where Γ = 2 a (yα -β x) -a 2 + 1 2 + 3 (ax + β) 2 + 3 a 2 (y + aα) 2 + 3 1 + a 2 2 . ( 6
)
As the two terms (1 + α 2 + β 2 ) and Γ clearly do not have any real solutions, this proves the lemma. (We discuss later how we found these terms.) Consider the system in the variables {a, x, y, α, β, u, v, w,t} that consists of the gros facteur, its partial derivatives, and the four 5 Recall that the singular points of a surface are the points where all partial derivatives are zero. > L:=[gros_fact, op(convert(grad(gros_fact, > [a,x,y,alpha,beta]),list)),1-u*(y+a*alpha), > 1-v*(a*x+beta),1-w*(1+alpha^2+beta^2),1-t*Gamma)]: > fgb_gbasis_elim(L,0,[u,v,w,t],[a,x,y,alpha,beta]); pack_fgb_call_generic: "Maple: 975.98 sec" [START_REF] Aurenhammer | Voronoi diagrams -a survey of a fundamental geometric data structure[END_REF] Table 1: For the proof of the Main Lemma.

equations 1 -u (y + a α) = 0, 1 -v (a x + β) = 0, 1 -w (1 + α 2 + β 2 ) = 0, 1 -t Γ = 0. (7)
The gros facteur and its partial derivatives have a common zero (real or complex) such that (y + a α) (a x + β) (1 + α 2 + β 2 ) Γ = 0 if and only if this system has a solution. This follows immediately from the fact that the equations ( 7) are linear in u, v, w,t.

The Gröbner basis of that system is reduced to the polynomial 1 (see Table 1) and thus the system has no solution (over the complexes). This concludes the proof.

The real difficulty in the proof of the Main Lemma is, of course, to find the equations ( 7) that rule out all the imaginary components of the set of singular points of the gros facteur. Computing these components is the actual key of the proof. We believe that the technique we used be of some interest to the community as it is rather generic and could be applied to other problems. We thus describe in Section 2.3 how these components were computed before finishing the study of the algebraic structure of the trisector, in Section 2.4.

About the proof of the Main Lemma

We show in this section how we computed, for the proof of the Main Lemma, the equations of (7) which correspond to hypersurfaces containing the zeros of the discriminant.

Basically, we proceed as follows. We start from the system of equations of the gros facteur and all its partial derivatives and use the following techniques to study its set of solutions, or more precisely to decompose it into components defined by prime ideals 6 . This could theoretically be done by a general algorithm computing a decomposition, however, all existing implementations are far from being capable of handling our particular problem or even a simpler sub-problem (see Remark 8).

the (reduced) Gröbner basis of some system contains a polynomial which has a factor, say F, the solutions of the system splits into two components, one of which such that F = 0, the other such that F = 0. We study separately the two components. One is obtained by adding the equation F to the system and the other is obtained by adding the equation 1t F eliminating the variable indeed, there is a one-to-one correspondence between the solutions of the initial system such that F = 0 and the solutions of the system augmented by 1t F. Sometimes, frequently in our case, the component F = 0 is empty, which corresponds to the situation where the elimination of t results in the polynomial 1 (inducing the equation 1 0). Note that in some cases the system contains a polynomial which is a square, say F 2 , thus the component such that F = 0 is obviously empty and we can add F to the system without changing its set of solutions (this however changes the ideal). This operation 6 An ideal I is prime if PQ ∈ I implies P ∈ I or Q ∈ I . of adding F to the system frequently adds embedded components to the variety of solutions which explains why, later on in the process, empty components are frequently encountered when splitting into two components.

Our computations, presented in the full version of the paper, are performed in Maple [START_REF]Waterloo Maple Software[END_REF] using the Gröbner basis package FGb developed by J.-C. Faugère [START_REF] Gb/Fgb | [END_REF] .

We use two functions, fgb_gbasis(sys,0,vars1,vars2) and fgb_gbasis_elim(sys,0,var1,var2) 7 , that compute Gröbner bases of the system sys; first uses a degree reverse lexicographic order (DRL) by blocks on the variables of vars1 and vars2 (where vars2 is always the empty set in our computation) and the second one eliminates the variable vars1 and uses a reverse lexicographic order on the variables of vars2. (The second parameter of the functions refer to the characteristic of the field, here 0.)

We never output the Gröbner bases which are too large to be useful, except in the case where the basis is reduced to 1 (when the system has no solution). We instead only report the first operand of each polynomial of the base; an operand means that the polynomial is the product of at least two factors; an operand ˆmeans that the polynomial is a power of some polynomial; an operand + means that the polynomial is a sum of monomials.

Our computation goes as follows. We first simplify our system by considering a = 2 because otherwise the Gröbner basis computations are too slow and use too much memory to be performed successfully. We first see after computing, bs 1 , the Gröbner basis of our system, that y + 2α appears as a factor of one polynomial. This splits the solutions into those such that y + 2α = 0 and the others. We will study separately (in Lemma 9) the former set of solutions and we only consider here the solutions such that y+2α = 0. This is done by adding the polynomial 1u (y + 2α) to the system, where u is a new variable; indeed there is a one-to-one correspondence between the solutions of the initial system such that y + 2α = 0 and the solutions of the resulting system.

The term y + 2α corresponds fairly clearly to the polynomial y + a α with a = 2, and because of the symmetry of our problem we also study separately the solutions such that a x + β = 0. Since we assumed a = 2, we only consider here the solutions such that 2 x + β = 0, by adding to the system the polynomial 1v (2 , x + β). Finally, we also add 1w (1 + α 2 + β 2 ) to the system, without changing its set of real of real roots; we do this because the term 1 + α 2 + β 2 appears in the leading coefficient of D(λ) which suggests that some component of solutions (without any real point) might be included in 1 + α 2 + β 2 . (It should be noted that adding this polynomial to the system changes the resulting Gröbner basis, which shows that this addition indeed removes some imaginary component from the system.) We compute the Gröbner basis, bs 2 , of that system, eliminating the variables u, v, w, which gives a system of four polynomials of degree six.

We then compute the Gröbner basis of bs 2 , eliminating the variable x. This gives a basis bs 3 which is reduced to one polynomial of the form P 2 . We thus add P to the system bs 2 (we do not add it to bs 3 since bs 3 does not depend on x). The Gröbner basis, bs 4 , of the new system contains several polynomials that are products of factors. We see that if we add to the system the constraint that the third factor of the first polynomial is not zero, the resulting system has no solution. We thus add this factor to the system and compute its Gröbner basis bs 5 . We operate similarly to get bs 6 . The basis bs 6 contains no product or power and we compute its Gröbner basis, bs 7 , eliminating y (eliminating x gives no interesting basis).

The last polynomial of bs 7 is a power and we proceed as before to get bs 8 . We proceed similarly until we get to the basis bs 12 .

The basis bs 12 consists of three polynomials of degree four (which is a simplification over bs 2 which consists of four polynomials of degree six). We observe that the last polynomial of bs 12 is

Γ 2 = (4 y α -4 β x -3) 2 + 3 (2 x + β) 2 + 12 (y + 2 α) 2 + 75,
which is always positive over the reals.

We have thus proved that all the complex solutions, such that a = 2, of the initial system (the gros facteur and all its partial derivatives) satisfy

(1 + α 2 + β 2 ) (y + 2α) (2x + β) Γ 2 = 0.
Finally, to get the polynomial Γ of Formula ( 6), we performed the same computation with a = 3 and a = 5 and guessed Γ as an interpolation of the polynomials Γ 2 , Γ 3 , and Γ 5 .

Note that all the computation for a fixed a takes roughly eight minutes of elapsed time on a regular PC. REMARK 8. All the computations from bs 2 to bs 12 amounts to finding polynomials that have a power which is a combination of the elements of bs 2 (i.e. which are in the radical of the ideal generated by bs 2 ). Thus these computations would be advantageously replaced by a program computing the radical of an ideal 8 . Unfortunately, all available such programs fail on the ideal generated by bs 2 either by exhausting the memory or by running unsuccessfully during several days and ending on an error. It is therefore a challenge to improve these programs in order to do this computation automatically.

Algebraic structure of the trisector, Part II

We proved in the Main Lemma that the discriminant ∆ is equal to zero only if y + a α = 0 or a x + β 0. We in this section that if ∆ = the trisector is a cubic a line that do not intersect. We then show that the trisector always contains four simple real points at infinity and conclude that the trisector is always to four lines that do not pairwise intersect.

LEMMA 9. The discriminant ∆ is equal to zero if and only if y

= -a α and x = β (2 a 2 + 1) ± 2 a 2 (1 + a 2 ) (α 2 + β 2 + 1) a , or (8) x = - β a and y = α (2 + a 2 ) ± 2 (1 + a 2 ) (α 2 + β 2 + 1) a . (9)
PROOF. By the Main Lemma, ∆ = 0 implies y + a α = 0 or a x + β = 0. Substituting y by -a α in ∆ gives an expression of the form f 0 f 2 1 . Similarly, substituting x by -β/a in ∆ gives an expression of the form g 0 g 2 1 (recall that a = 0 since the lines are not coplanar, by assumption). It follows that ∆ = 0 if and only if y + a α = f i = 0 or a x + β = g i = 0, for i = 0 or 1. The f i and g i are polynomials of degree two in x and y, respectively. Solving f 1 = 0 in terms of x directly yields that the system y + a α = f 1 = 0 is equivalent to [START_REF] Cohen | A course in computational algebraic number theory[END_REF]. Similarly, solving g 1 = 0 in terms of y yields [START_REF] Culver | Computing the Medial Axis of a Polyhedron Reliably and Efficiently[END_REF]. On the other hand, we prove that the solutions of y + a α = f 0 = 0 and a x + β = g 0 = 0 are included in the set of solutions of ( 9) and ( 8), respectively, which concludes the proof. Because of lack of space, we omit here this proof. LEMMA 10. If ∆ = 0, the trisector of 1 , 2 , and 3 consists of a cubic and a line that do not intersect in real space.

PROOF. By Lemma 9, ∆ = 0 if and only if System (8) or ( 9) is satisfied. By symmetry of the problem (we omit here the specification of the symmetry) we only need to consider one of the components of ( 8) and ( 9). Hence, it is sufficient to show that the system 8 The radical of an ideal I is the ideal {x | x n ∈ I for some n ∈ N}.

y = -a α, x = β (2 a 2 +1) a + 2 (1 + a 2 ) (α 2 + β 2 + 1)
implies that the trisector consists of a cubic and a line that do not intersect. We assume in the following that this system is satisfied and that ∆ = 0. We refer to the full version of the paper for the computations.

We first show that the characteristic polynomial of the pencil generated by the bisectors is always strictly positive. Recall that the characteristic polynomial is never negative (see Lemma 4). It is thus sufficient to prove that it is never zero, or equivalently, that its product with its algebraic conjugate (obtained by changing the sign of (1 + a 2 ) (α 2 + β 2 + 1)) is never zero. This product is a polynomial T in a, α, β, λ. We compute, similarly as in the proof of Lemma 4, at least one point per connected component of the real semi-algebraic set {χ = (a, α, β, λ) ∈ R 4 | T (χ) -1 2 < 0}. The resulting set of points is empty, hence T (χ) is always greater or equal to 1/2. It thus follows that the characteristic polynomial is always strictly positive.

Since the characteristic polynomial D(λ) is always strictly positive and its discriminant ∆ is zero, D(λ) admits two (conjugate) double imaginary roots. Let 1 and λ 2 denote these two roots. Recall that D(λ) = det P(λ) with P(λ) = λQ 1,2 + Q 1,3 where Q i, j is matrix associated with the hyperbolic paraboloid H i, j . It folfrom the classification of the intersection of quadrics [12, Table 4] that either (i) P(λ 1 ) and P(λ 2 ) are of rank 3 and the trisector H 1,2 ∩ H 1,3 of a cubic and a line that do not intersect or (ii) P(λ 1 ) and P(λ 2 ) are of rank 2 and the trisector consists of two secant lines.

We now prove that P(λ 1 ) and P(λ 2 ) are of rank 3. We compute the Gröbner basis of all the 3 × 3 minors of P(λ) and of the polynomial 1 -tΨ with

Ψ = (1 + a 2 ) (1 + α 2 + β 2 ) (a x -y -β + a α) (y + a x -a α -β).
The basis is equal to 1, thus the 3 × 3 minors of P(λ) are not all simultaneously equal to zero when Ψ = 0. Furthermore, = 0 for any x, y, a, α, β in R such that the lines 1 , 2 , and 3 are pairwise skew (see [START_REF] Boissonnat | Triangulations in CGAL[END_REF] and the proof of Lemma 7). Thus the rank of P(λ) is at least 3. The rank of P(λ i ), i = 1, 2, is thus equal to 3 since det P(λ i ) = 0. We can thus conclude that when ∆ = 0 the trisector consists of a cubic and a line that do not intersect in real space.

We now state a proposition that shows that the trisector admits four asymptotes that are pairwise skew and gives a geometric characterization of their directions. PROPOSITION 11. The trisector of 1 , 2 , and 3 intersects the plane at infinity in four real simple points. Furthermore, the four corresponding asymptotes are parallel to the four trisector lines of three concurrent lines that are parallel to 1 , 2 , and 3 , respectively.

PROOF. The trisector is the intersection of two hyperbolic paraboloids. Any hyperbolic paraboloid contains two lines at infinity. Hence the intersection, at infinity, of any two distinct hyperbolic paraboloids is the intersection of two pairs of lines. The intersection of these two pairs of lines consists of exactly four simple real points unless the point of intersection of the two lines in one pair lies on one line of the other pair. Because of lack of space, we omit here the proof that this cannot happen under our assumptions and the characterization of the four asymptotes. THEOREM 12. The trisector of three lines in general position consists of four infinite smooth branches of a non-singular quartic or of a cubic and a line that do not intersect in real space.

PROOF. As mentioned in the beginning of Section 2.2, the trisector of tree lines consists of a smooth quartic unless the discrim- inant ∆ is zero. Lemma 10 and Proposition 11 thus yield the result.

Topology of the Voronoi diagram

We now prove that the set of triplets of lines in general position is connected and conclude the proof of Theorem 1.

LEMMA [START_REF] Etzion | Computing voronoi skeletons of a 3-d polyhedron by space subdivision[END_REF]. There is a one-to-one correspondence between the set of ordered triplets of lines (in general position) and the set of affine frames of positive orientation.

PROOF. Consider three lines 1 , 2 , and 3 in general position and refer to Figure 3. For the three choices of pairs of lines i , j , consider the plane containing i and parallel to j , the plane containing j and parallel to i , and the region bounded by these two parallel planes. The general position assumption implies that these regions have non-empty interiors and that no three planes are parallel. The intersection of these three regions thus defines a parallelepiped. By construction, each of the lines 1 , 2 , and 3 contains an edge of that parallelepiped. These lines are pairwise skew thus exactly two vertices of the parallelepiped are not on the lines. Each of these two points induces an affine frame centered at the point and with basis the three edges of the parallelepiped oriented from the point to the lines 1 , 2 , and 3 , in this order. One of the point (C on the figure) defines a frame of positive orientation, the other defines a frame of negative orientation (C on the figure). This construction exhibits a one-to-one correspondence between the set of ordered triplets of lines (in general position) and the set of affine frames of positive orientation, which concludes the proof. COROLLARY 14. The set of triplets of lines in general position is connected.

THEOREM 15. The topology of the Voronoi diagram of three lines in general position is invariant.

PROOF. Consider three lines in general position and a bisector of two of them. The bisector is a hyperbolic paraboloid which is homeomorphic to a plane. The trisector lies on the bisector and it is homeomorphic to four lines that do not pairwise intersect, by Theorem 12. Hence the topology of the regions that lie on the bisector and are bounded by the trisector is invariant by continuous deformation on any connected set of triplets of lines (in general position). The topology of these regions is thus invariant by continuous deformation on the set of all triplets of lines in general position (by Corollary 14). It follows that the topology of the two-dimensional cells of the Voronoi diagram is invariant by such a continuous deformation. The Voronoi diagram is defined by the embedding in R 3 of its two-dimensional cells, hence its topology is also invariant by continuous deformation.

T 13 < T 13 T 13 < T 13 PROOF OF THEOREM 1. Theorem 1 follows from Theorems 12 and 15 and from the computation of an example of a twodimensional cell of the Voronoi diagram (for instance the one shown in Figure 1).

T 13 < U 12 < T 23 T 23 < T 23 T 23 < T 23 T 13 < U 13 T 13 < T 12 < T 23 U 23 < T 23 C 0 C 3 C 1 C 2 X Y T 1 3 < T 1 3 T 2 3 < T 2 3

PROPERTIES OF THE VORONOI DIAGRAM AND ALGORITHMS

We present here some fundamental properties of the Voronoi diagram and algorithms for separating the two components of each two-dimensional Voronoi cell and the four components of the cell of dimension one. Because of the lack of space, we omit all proofs (see the full paper for proofs).

We start by presenting in Proposition 16 two properties, one on the asymptotes of the trisector and one on the incidence relations between cells, which directly yield an unambiguous labeling of the components of the trisector. We then present two fundamental properties of the trisector. Finally, we present algorithms for separating the two components of each two-dimensional Voronoi cell and the four components of the cell of dimension one.

We consider any three lines 1 , 2 , and 3 in general position (pairwise skew and not all parallel to a common plane) and an associated Cartesian coordinate system (X,Y, Z) such that the Z-axis is parallel to the common perpendicular of 1 and 2 and such that the X and Y are parallel to the two bisector lines, in a plane perpendicular to the Z-axis, of the projection of 1 and 2 onto that plane. 9 Note that the orientations of the axes are not specified (except for the fact that the frame has a positive orientation) and that the X and Y -axes can be exchanged.

Labeling of the four branches of the trisector. Let V i j denote the two-dimensional Voronoi cell of lines i and j and let U i j and T i j denote the connected components of V i j that are bounded by one and three arcs of the trisector, respectively (see Figure 1). PROPOSITION 16. Exactly one of the four branches of the trisector of three lines in general position admits only one asymptote. Let C 0 denote this branch. Each cell U i j is bounded by a branch distinct from C 0 and every such branch bounds a cell U i j .

Let C k , k = 1, 2, 3, denote the branches of the trisector that bound the component U i j , i, j = k. The labeling of the four branches of the trisector by C 0 , . . . ,C 4 is unambiguous.

Note that differentiating between C 1 and C 2 cannot be done, as far as we know, by only looking at the cell V 12 (see Figure 1) but can be done by looking at the other cells V 13 and V 23 . More precisely, differentiating between C 1 and C 2 on Figure 1 can be done by computing a vertical ordering of the components U i j and T i j ; the branch C k is then characterized as the branch for which U i j appears only on one of its side (see Figure 4).

Properties of the trisector. We now present two important properties of trisector of the Voronoi diagram of three lines in general position. In particular, we prove the Monotonicity Property in Proposition 18.

PROPOSITION 17. The orthogonal projection of the trisector of 1 , 2 , and 3 onto the XY -plane has two asymptotes parallel to the X-axis and two asymptotes parallel to the Y -axis.

PROOF. By proposition 11, the four asymptotes of the trisector are parallel to the four trisector lines of three concurrent lines parallel to 1 , 2 , and 3 . The bisector to two lines through the origin and parallel to 1 and 2 is the pair of planes of equation XY = 0. the asymptotes of the trisector are parallel to lines that lie in the pair of planes XY = 0. The orthogonal projection of the asymptotes on the XY -plane are thus parallel to the X-or Y -axis. It follows that the number of asymptotes (in projection) that are parallel to the Xaxis (resp. Y -axis) is invariant by continuous deformation on any connected set of triplets of lines in general position. The result follows from the fact that, on a particular example (see Figure 1), there are two asymptotes parallel to the X-axis and two others parallel to the Y -axis and that the set of triplets of lines in general position is connected (Corollary 14).

We assume in the following that the asymptote of C 0 is parallel to the Y Z-plane (as in Figure 1) by exchanging, if necessary, the role of X and Y . PROPOSITION 18. Every branch of the trisector of 1 , 2 , and 3 is monotonic with respect to the Y -direction (or every branch is monotonic with respect to the X-direction).

PROOF. Let P denote any plane parallel to the XZ-plane. The arc C 0 intersects plane P an odd number of times (counted with multiplicity) since C 0 has only one asymptote (Proposition 16) which is parallel to the Y Z-plane. Furthermore, by Proposition 17, the trisector has two other asymptotes parallel to the XZ-plane. plane P intersects the trisector in two points at infinity and C 0 an odd number of times (in affine space). The trisector thus intersects P in at least three points in real projective space. There are thus four intersection points (in real projective space) since there are four intersection points in complex space (since the trisector is of degree four) and if there was an imaginary point of intersection, its conjugate would also be an intersection point (since the equations of the plane and quadrics have real coefficients) giving five points of intersection.

the trisector intersects plane P in two points in R 3 , one of which lies on C 0 . Since there are an odd number of intersection points on C 0 , plane P intersects C 0 exactly once and any other branch exactly once.

Algorithms. consider here any three lines in general position (pairwise skew and not all parallel to a common plane). We present an algorithm for determining a rational linear test for separating the two connected components of each two-dimensional Voronoi cell. As we will see, this algorithm leads directly to another rational linear test for separating the four connected components of the cell of dimension one.

We start by presenting an algorithm for determining a plane separating the two components of any two-dimensional Voronoi cell. Refer to Figure 5(a). This plane may not be rational; indeed, as we shall see in Proposition 20, it is possible that no rational separating plane exists.

Linear test for separating the two connected components of a two-dimensional Voronoi cell.

Input: three lines 1 , 2 , and 3 in general position and = j ∈ {1, 2, 3}.

Output: a half-space H i j that strictly contains U i j and whose strictly contains T i j . (i) Determine a Cartesian coordinate system (X,Y, Z) such that the Z-axis is parallel to the common perpendicular of i and j and such that the X and Y -axes are parallel to the two bisector lines, in a plane perpendicular to the Z-axis, of the projection of i and j onto that plane. In this frame, compute all the critical values of the trisector with respect to the X-axis. If there is no critical value, exchange the X-and Y -axes (and compute the critical values with respect to the new X-axis). (iii) Compute the X-values of the two trisector asymptotes that are parallel to the Y Z-plane. If the minimum of these valis smaller than the smaller critical value, then change the orientation of the X-axis. Denote by X 1 the smallest critical value (with respect to the X-axis) of the trisector and by X 2 the smallest of the other critical values and of the two asymptote X-values. (iv) Pick a value x in (X 1 , X 2 ). The half-space, H i j , of equation X < x contains U i j and the half-space X > x contains T i j .

The algorithm requires computing the critical values of the trisector with respect to the X and Y -directions. We proved (in Propo-18) that the trisector has no critical values in one of these directions. We show below that the trisector admits at most four critical values with respect to the other direction. We consider below the coordinate system obtained after Step (ii) of the algorithm above.

LEMMA 19. The trisector has three or four critical values with respect to the X-direction. Moreover, the trisector has one critical point on C 3 , one on C 1 ∪ C 2 , and either two on C 0 or C 0 is a line perpendicular to the X-axis.

The following proposition shows that the separating plane computed in the above algorithm may not be rational. PROPOSITION 20. There exist three rational lines for which the two connected components of any two-dimensional Voronoi cell cannot be separated by a rational plane.

We now present an algorithm for determining a rational linear semi-algebraic test for separating the two components of any Rational linear test for separating the two connected components of a two-dimensional Voronoi cell.

X Y U 12 T 12 C 0 C 3 C 1 C 2 X 1 X 2 H 12 (a) X Y U 12 T 12 X 1 X 2 H 1 2 ∩ H 1 2 Y 1 Y 2 A B C (
Input: three rational lines 1 , 2 , and 3 in general position in a coordinate system ( X, Ỹ , Z) and i = j ∈ {1, 2, 3}.

Output: two rational half-spaces H i j and H i j such that H i j ∩ H i j strictly contains U i j and its complement strictly contains T i j . (i-iii) Idem as in the previous algorithm.

(iv) Compute the two Y -values of the two trisector asymptotes that are parallel to the XZ-plane. Let Y 1 < Y 2 denote these two values. (v) Determine a point A with rational coordinates in the original X, Ỹ , Z)-frame such that its X-, Y -, and Z-coordinates in the (X,Y, Z) frame are in (X 1 , X 2 ), in (Y 1 ,Y 2 ), and equal to 0, respectively; let X A denote its X-coordinate in (X,Y, Z) frame. (vi) Determine two points B and C with rational coordinates in the original ( X, Ỹ , Z)-frame such that X-, Y -, and Zcoordinates in the (X,Y, Z)-frame are, for B, in (X 1 , X A ), in (-∞,Y 1 ), and equal to 0, respectively, and for C, in (X 1 , X A ), in (Y 2 , +∞), and equal to 0, respectively. (vii) Let P i j (resp. P i j ) be the plane through A and B (resp. C) that is parallel to the Z-axis. Let H i j (resp. H i j ) be the open halfspace bounded plane P i j (resp. P i j ) that contains the point at infinity in the -X-direction.

REMARK 21. Note that, if the three input lines are not rational, the above algorithm remains valid except for the fact that the output half-spaces are not necessarily rational anymore (since the common perpendicular to i and j is not necessarily rational).

Separation of the four connected components of the trisector of three lines.

Consider three lines 1 , 2 , and 3 and the half-space H i j and H i j obtained by the above algorithm. Proposition 16 (and Remark 21) directly yields the following result. PROPOSITION 22. For any point p on the trisector of 1 , 2 , and 3 , if p belongs to both half-spaces H i j and H i j for some i = j ∈ {1, 2, 3} then p lies on C k (with k ∈ {1, 2, 3} distinct from i and j), otherwise p lies on C 0 . Furthermore, if the three input lines are rational, this linear semi-algebraic test is rational.

We conclude this section by proving Theorem 2. PROOF OF THEOREM 2. First, the algorithms of this section and Proposition 22 present some (rational) linear semi-algebraic tests for separating the connected components of the Voronoi cells of dimensions one and two. Second, we can compute, as described in Steps (i-ii) of the above algorithms, a direction in which every branch of the trisector is monotonic, which gives a linear test for ordering points on each trisector.

CONFIGURATIONS OF THREE LINES WHOSE TRISECTOR CONTAINS A LINE

We present a geometric characterization of the position of three lines in general position such that their trisector consists of a cubic and a line. In what follows, the parallelepiped and frame associated to the three lines are the one introduced in the proof of Lemma 13 (see Figure 3). We show that, if the trisector of three lines in general position contains a line, then the center O of the parallelepiped associated to the lines lies on the trisector line. Furthermore, this trisector line is the line through O and parallel to the interior trisector of the associated frame. Conversely, we also show that if the directions of the three input lines are not in some special configuration, then the trisector contains a line if and only if it contains the center of the associated parallelepiped. Because of lack of space, we omit the precise meaning of interior trisector, the description of the special configuration, and all proofs (see the full paper for details).

CONCLUSION

We presented a complete description of the Voronoi diagram of three lines in general position. We also presented some algorithms for determining a rational test for answering queries of the form, given a point, determine in which connected component of which Voronoi cell it lies. We also showed that points on a branch of the trisector of three lines can easily be ordered by comparing their coordinates in a particular direction, which is however not necessarily rational.

Figure 1 :

 1 Figure 1: Voronoi diagram of 3 lines 1 , 2 , and 3 in general position: (a) Voronoi 2D-face of 1 and 2 , i.e., set of points equidistant to 1 and 2 and closer to them than to 3 . (b) Orthogonal projection of a 2D-face on a plane P with coordinate system (X, Y); the plane's normal is parallel to the common perpendicular of 1 and 2 and the X and Y-axes are parallel to the two bisector lines (in P ) of the projection of 1 and 2 on P . The 2D-face is bounded by four branches of a non-singular quartic.

YOFigure 2 :

 2 Figure 2: Three lines in general position.

LEMMA 4 .

 4 The characteristic polynomial D(λ) is never negative.

  and the connected component containing χ 0 of the hypersurface D(χ) = v is included in the connected component C . Hence, a point in C can be found by computing a point in each connected component of D(χ) = v. It follows that we can compute at least a point in every connected component of the semi-algebraic set S defined by D(χ) < 0 by computing at least one point in every connected component of the real hypersurface defined by D(χ) = v

  k ) where (χ k ) k∈N is a sequence of points that goes to infinity while χ k • grad χ k D(χ k ) tends to zero. The generalized critical values are the critical values and asymptotic critical values. The set of generalized critical values contains all the extrema of function D, even those that are reached at infinity.4 Since S = R 6 , the boundary of C not empty and consists of points χ such that D(χ) = 0. The image of the connected set C by the continuous function D is an interval. Hence, zero is an endpoint of the interval D(C ). The other endpoint is either an extremum of D thus a generalized critical value) or minus infinity.

>

  Gamma:=(2*a*(y*alpha-x*beta)-(a^2-1))^2 > +3*(a*x+beta)^2+3*a^2*(y+a*alpha)^2+3*(a^2+1)^2;

3 Figure 3 :

 33 Figure 3: The parallelepiped formed by 1 , 2 , and 3 and the associated frame (C, v 1 , v 2 , v 3 ) of positive orientation.

Figure 4 :

 4 Figure 4: Vertical ordering of the connected components of the two-dimensional Voronoi diagram cells above each region induced by the projection of the trisector and the silhouette curves of the bisectors; the ordering over the small cell in the middle is T 13 < T 13 < T 23 < T 23 (i.e., a vertical line over that cell intersects twice T 13 and twice T 23 in that order).

b) Figure 5 :

 5 Separating the two components of a two-dimensional Voronoi cell. two-dimensional Voronoi cell of three rational lines. Refer to Figure 5(b).

By non-singular quartic, we mean an irreducible curve of degree four with no singular point in P 3 (C).

By rational linear test, we mean that the polynomials (whose signs determine the connected components) are of degree one in the coordinates of point p and have rational coefficients.

Recall that the (real) critical values of D the values of D at its critical points χ, i.e., the points χ at which the gradient of D zero. The asymptotic critical values are similarly defined as, roughly speaking, the values taken by D at critical points at infinity, that is, the values c ∈ R such that the hyperplane z = c is tangent to the surface z = D(χ) at infinity (this definition however only holds for two variables, i.e., χ ∈ R 2 ). More formally, the asymptotic critical values were introduced by Kurdyka et al.[START_REF] Kurdyka | Semialgebraic Sard theorem for generalized critical values[END_REF] as the limits of

The function gbasis(sys,DRL(var1,var2),elim) with or without the last argument elim can also be used alternatively of these two functions

Note that this setting is slightly different than the one described in Section 2.1 since, here, any triplet of three lines in general position can be moved continuously into another while the associated frame moves continuously; however, if the initial and final triplets of lines are in the setting of Section 2.1, it is not necessarily possible to ensure that, during the motion, all triplets of lines remain in this setting.

Future work includes the characterization of the topology of the Voronoi diagram of three lines that are not in general position. We believe that the proof techniques we presented here work similarly for this problem. A challenging problem is to study Voronoi diagrams of up to six lines; this is of interest for the general case of n lines because the arcs of such diagrams are defined by five lines. Finally, the two major problems remain the determination of the complexity of Voronoi diagrams of n lines and the design of efficient algorithms for computing Voronoi diagrams of lines, segments, triangles, or polyhedra.


Martine Cadot
email: martine.cadot@loria.fr

Pascal Cuxac
email: pascal.cuxac@inist.fr

Alain Lelu
email: alain.lelu@jouy.inra.fr

Random simulations of

Keywords: Text Mining, Randomization Tests, Significant Itemsets, Statistical Interaction, Multiple Comparison

published or not. The documents may come

Introduction : setting the problem

In a knowledge discovery task, knowledge nuggets are brought to light in the shape of itemsets, i.e. "interesting" conjunctions of boolean variables from which association rules may be derived. Presently, more than fifty different measures are used for trying to establish the quality of association rules [START_REF] Guillet | Mesure de qualité des connaissances en ECD, Cours donné lors des journées EGC 2004[END_REF]. The difficulty to use them comes from the diversity of their own (or common) semantics [START_REF] Lenca | Critères d'évaluation des mesures de qualité en ECD[END_REF], but also from the uncertainty about their statistical robustness [START_REF] Press | The role of Bayesian and frequentist multivariate modeling in statistical Data Mining[END_REF]. Two reasons behind these difficulties: 1) the concept of independance is simple to understand for 2 variables, but is not so obvious beyond [START_REF] Franois | Modèles et données : une introduction la Statistique uni-, bi-et trivariée[END_REF]; the concept of dependance is still worse, as many definitions are available... 2) one catches easily the concept of interaction for 2 variables faced to a third one, but the extension to three and more is nothing but evident [START_REF] Winer | Statistical principles in experimental design[END_REF]. A k-itemset expresses an imprecise notion of relation between k variables, and it may refer implicitly to the first viewpoint or the second. This is why we have developped two distinct inspiration lines for this unique reality. Moreover, combinatorial explosion is a recurrent issue for the itemsets extraction algorithms in this domain. We have developed two ideas for tackling the overall difficulty:

Idea 1: Given a text collection, two frequent words are much more likely to occur altogether in a text than two infrequent ones. Simulating random variants of the presence/absence data, it is thus possible to evaluate whether or not the support of any itemset is too small (or too large, in the case of rare itemsets) to be fortuitous. Our TourneBool method determines a context-dependant confidence interval for the support of each 2-itemset, thus selecting the only statistically validated ones.

Idea 2: A, B, C being three words in a text collection, if A and B often occur simultaneously in the same texts, the number of texts with A and C together does not differ much from the one with B and C together. For each itemset, our Midova method yields 1) the variation share left to the support of its super-itemsets (Midova residue index ), 2) the deviation between its support and the expected median support, given its sub-itemsets (Midova gain index ).

Hence our operating sequence: Given a set of objects characterized by a set of boolean features, our goal is to mine the only informative k-associations between features (k-itemsets):

• selecting the only statistically valid 2-itemsets, those "too (in)frequent" to be hazardous (TourneBool method), • for k = 2, 3, 4, ... selecting the only k-itemsets highlighted by an appreciable support variation left by their sub-itemsets (Midova method).

Statistical validation of 2-itemsets connections

TourneBool method:

• belongs to the class of randomization tests [START_REF] Manly | Randomization, Bootstrap and Monte Carlo methods in Biology[END_REF],

• validates the significant 2-itemsets with a "cascade-permutation" method [START_REF] Cadot | A Simulation Technique for extracting Robust Association Rules[END_REF][START_REF] Cadot | Extraire et valider les relations complexes en sciences humaines : statistiques, motifs et règles d'association Thèse d'informatique[END_REF].

The principle is to generate a randomized version of the initial datatable, under the constraint of keeping the same margins (row and column sums) as the original datatable (see figure 1). We have shown in [START_REF] Cadot | Une optimisation de l'extraction d'un jeu de règles s'appuyant sur les caractéristiques statistiques des données[END_REF] that this constraint was mandatory to distinguish structural effects (associations due to the sole effect of margins of the datatable) from meaningful ones. This process is repeated at least a hundred times. For each 2-itemset in the initial data, the distribution of its support in the randomized tables is computed. The initial value is compared to the 2.5% head and 2.5% tail values of the distribution (in case of 95% confidence choice): if it falls outside this interval, the relation is declared significant, positively or negatively. TourneBool algorithm: Let M a boolean matrix (n, p), with n objects in rows and p variables in columns.

Main : TourneBool

• 1. generate q randomized versions of M • 2. for each column pair (i, j)

determine the lower and upper bound of the support's confidence interval after the list of the support values in the randomized matrices. -3 cases:

* if the original itemset support in M stays in between this interval, it is declared unsignificant and is thus eliminated, * if it is lesser than the lower bound, it is declared significantly rare, and is thus kept on, * if it is greater than the upper bound, it is declared significantly frequent, and is thus kept on.

Building q randomized versions of M :

• choose a number r of rectangular exchanges to execute • 1. copy M to M c • 2. repeat q times : -2.1 repeat r times : * choose at random with replacement a row pair and a column pair * if the zeros and ones alternate at the corners of this rectangle in M c, then modify M c moving each value into its complement to 1, else do nothing. -2.2 store M c Building the confidence interval, at risk alpha, of an itemset (i, j) of M :

• 1. for each randomized version of M compute the support of the itemset (i, j) (dot product of the two columns) Store all the supports in a list. • 2. sort the list in ascending order. The lower bound is the list element with rank q * alpha/2, and the lower bound the one with q * (1alpha)/2 rank.

MIDOVA algorithm and indices

Midova : Given three yet determined itemsets A, B, C, the MIDOVA method [START_REF] Cadot | Règles d'association avec une prémisse composée : mesure du gain d'information[END_REF] looks for the variation interval of the ABC itemset support, in the framework of fixed support constraints for its sub-itemsets AB, AC, BC. Counts are established considering elementary unitary swaps (A → nonA, nonA → A, B → nonB, ...)

Midova indices for a k-itemset M : Combinatorial considerations developped in [START_REF] Cadot | Extraire et valider les relations complexes en sciences humaines : statistiques, motifs et règles d'association Thèse d'informatique[END_REF] show that: where g and r are expressed with the same units as the support s, i.e as a number of objects. A reasonable choice for the significance threshold of r seems r ≥ 2. It is worth to notice that Midova parametered with the s ≤ t, t being a given positive threshold, and r ≥ 2, amounts to the A-priori algorithm [START_REF] Agrawal | Fast Discovery of Association Rules[END_REF][START_REF] Bastide | Data mining : algorithmes par niveau. techniques d'implantation et applications[END_REF], intrinsically devoted to frequent itemsets. The choice of s ≤ 0 yields infrequent itemsets, i.e. pairs, triplets, etc. of "opposite" variables, less encountered than expected at random. These interesting negative relations are generally not considered in the knowledge extraction literature.

•

Midova algorithm

• 0) Initializing: A threshold value is chosen as the measure of a negligible gap, expressed as a number of objects (0, 1, 2, ...) • 1) Level 1 (1-itemsets, i.e. boolean variables): the support s of each itemset is somewhere between 0 and N . Compute:

the difference to the "neutral center" N/2 of this interval, -the variation share left to the supports of its super-itemsets (i.e. 2-itemsets), which writes s if s > N/2, else Ns, then the 1-itemsets for which this share is negligible (s ≤ e) or almost equal to N (s ≥ N -e) have exhausted their variation potential, and are therefore eliminated in the sequel of the process.

• 2) Level k; -For each k-itemset M k issued from the candidate itemsets of lower order k -1, the support s of M k is stored, and its variation interval [sl ; su] is computed, as well as the difference with the center of this interval, and the variation share left to the superitemsets of higher order: this amount is the Midova residue (i.e. the difference with the closest interval limit sl or su). If this amount is negligible, the current itemset is considered to have exhausted its variability potential, and is thus eliminated from the list of combinable itemsets at the next k + 1 stage. -While k-itemsets stay uneliminated: increment k and return to 2).

4 Application to a real text database: In the left part of the figure 3, the word distribution in the abstracts appears to be approximately binomial, with a central value of about 50 words per text. The right part shows the very unequal, Zipfian, distribution of word counts in the corpus, as usual in language statistics.

Overall results on our "Geotechnics" texts set

With TourneBool (alpha-risk=0.01) and Midova (residue r ≥ 5), all the itemsets are extracted, whatever their support (s ≥ 0). Starting from the 8477 variables (words), it yields :

• step 1, Midova: given 8477 itemsets, 1707 are kept (with r ≥ 5) for composing 2-itemsets.

• step 2, TourneBool: given 1,456,071 2-itemsets, 7712 significant ones are kept with 0.01. alpha risk. • step 3, Midova: 5046 2-itemsets are kept on (with r ≥ 5) for setting up 3-itemsets • step 4, Midova: starting from 4160 3-itemsets, 2214 are kept on (with r ≥ 5) for setting up 4-itemsets The process is represented in the figure 4 in full lines, and in figure 5 by black bars, which show that our process clearly outperforms A-priori method by the number and length of itemsets criteria.

Interpretation of our "Geotechnics" k-itemsets

We will limit our interpretation trial to the significant 2-itemsets issued from TourneBool, with extreme Midova-g values. we have selected a few interesting examples to our domain expert's eyes:

• 2-itemsets with support lesser than expected, and with strong negative gain:

-'rock', 'soil', Mr=-163, support=25 -'site', 'theory', Mr=-81, support=3 • 2-itemsets with support greater than expected, and with strong positive gain:

-'pore', 'pressure', Mr=51, support=68 -'conductivity', 'hydraulic', Mr=17, support=21 -'ash', 'fly', Mr=9, support=9 • 4-itemsets with strong positive gain:

-'model', 'modelling', 'finite', 'numerical', Mr=28, support=10 • Words contributing to significantly frequent 2-itemsets with 'site' (with M r ≥ 4): 'amplification', 'amplify', 'ground-motion', 'near-surface', 'recording', 'SEC', 'Shear-wave', 'spectral', 'spectrum', 'S-wave', 'unconsolidated'.

The expert has admitted that these associated terms evoke the concept of seism.

Conclusion

Computer efficiency: Implemented as sparse matrices processing, out of any particular optimization effort, the CPU efficiency seems promising: less than 15 minutes on a standard 2.2 GHz PC for the 200 simulations part of a TourneBool run, on our 1000 X 8500 Geotechnics data; a few minutes for Midova.

• Compared to A-priori, the TourneBool-Midova sequence has reduced the number of "interesting" k-itemsets from 126, 200 to 13, 200, i.e. about two orders of magnitude. • TourneBool has divided the overall width of the k-itemsets pyramid by 3.6, at the type-1 error risk of 0.01 (see figure 5). • Midova has reduced the overall height of the k-itemsets pyramid from k = 8 to k = 6 (with r ≥ 5).

Advantages and limits: Our TourneBool algorithm allows one to build a statistical test well-adapted to data mining (many variables, data-flows...):

• it works for small amounts of variables as well as big ones; doing so, it tackles the "multiple comparison" problem [START_REF] Jensen | Multiples comparisons in induction algorithms[END_REF],

• it fits to any probability distribution, with no need to explicitly specify this distribution [START_REF] Droesbeke | Inférence non paramétrique, les statistiques de rangs[END_REF] ("distribution-free" property).

Our choice for the central value of the gain is not yet ascertained, thus strong conclusions can be drawn for the only extreme positive or negative values of the gain. Negative interactions are tricky to interpret and merit further investigations.

Fig. 1 .

 1 Fig. 1. Example of a cascade exchange (C, squares), and a rectangular exchange (S, circles).

  the gain index g is a function of the support s of the k-itemset M , of its length k, and of the center c of the support variation interval, whose lower an upper bounds are respectively sl and su : g = 2 k-1 (sc) where c = (sl + su)/2 -sl = smin("odd" zones) ; see figure 2 -su = s + min("even" zones) • the residue index r is a function of k, s, sl, su: r = 2 k-1 min(|s -sl|, |s -su|)

Fig. 2 .

 2 Fig. 2. Distribution of 60 subjects over 3 boolean features.

4. 1

 1 Presentation of our "Geotechnics" database

Fig. 3 .

 3 Fig. 3. Distribution of the abstracts and words in the corpus

Fig. 4 .

 4 Fig. 4. Comparison TourneBool+Midova vs. A-priori (1)

Fig. 5 .

 5 Fig. 5. Comparison TourneBool+Midova vs. A-priori (2)