Hazel Everett

Sylvain Lazard

William Lenhart
email: lenhart@cs.williams.edu

Linqiao Zhang
email: lzhang15@cs.mcgill.ca.

On the Degree of Standard Geometric Predicates for Line Transversals in 3D

In this paper we study various geometric predicates for determining the existence of and categorizing the configurations of lines in 3D that are transversal to lines or segments. We compute the degrees of standard procedures of evaluating these predicates. The degrees of some of these procedures are surprisingly high (up to 168), which may explain why computing line transversals with finite-precision floating-point arithmetic is prone to error. Our results suggest the need to explore alternatives to the standard methods of computing these quantities.

Introduction

Computing line transversals to lines or segments is an important operation in solving 3D visibility problems arising in computer graphics [START_REF] Bronnimann | Lines and free line segments tangent to arbitrary three-dimensional convex polyhedra[END_REF][START_REF] Duguet | Robust epsilon visibility[END_REF][START_REF] Durand | The visibility skeleton: a powerful and efficient multi-purpose global visibility tool[END_REF][START_REF] Durand | The 3D visibility complex[END_REF][START_REF] Efrat | On incremental rendering of silhouette maps of a polyhedral scene[END_REF][START_REF] Plantinga | Visibility, occlusion, and the aspect graph[END_REF]. In this paper, we study various predicates and their degrees concerning line transversals to lines and segments in 3D.

A predicate is a function that returns a value from a discrete set. Typically, geometric predicates answer questions of the type "Is a point inside, outside or on the boundary of a set?". We consider predicates that are evaluated by boolean functions of more elementary predicates, the latter being functions that return the sign (-, 0 or +) of a multivariate polynomial whose arguments are a subset of the input parameters of the problem instance (see, for instance [START_REF] Boissonnat | Robust plane sweep for intersecting segments[END_REF]). By degree of a procedure for evaluating a predicate, we mean the maximum degree in the input parameters among all polynomials used in the evaluation of the predicate by the procedure. In what follows we casually refer to this measure as the degree of the predicate. We are interested in the degree because it provides a measure of the number of bits required for an exact evaluation of our predicates when the input parameters are integers or floating-point numbers; the number of bits required is then roughly the product of the degree with the number of bits used in representing each input value.

In this paper, we first study the degree of standard procedures for determining the number of line transversals to four lines or four segments in 3D; recall that four lines in R 3 admit 0, 1, 2 or an infinite number of line transversals and that four segments admit up to 4 or an infinite number of line transversals [START_REF] Brönnimann | Transversals to line segments in threedimensional space[END_REF]. We also consider the predicate for determining whether a minimal (i.e., locally shortest) segment transversal to four line segments is intersected by a triangle. These predicates are ubiquitous in 3D visibility problems. The latter predicate, for instance, can be used for determining whether two triangles see each other in a scene of triangles (that is, for determining whether there exists a segment joining the two triangles and that does not properly intersect any of the other triangles). Finally, we study the predicate for ordering planes through two fixed points, each plane containing a third rational point or a line transversal to four segments or lines. This predicate arises in the rotating plane-sweep algorithm that computes the minimal free segments tangent to four among k convex polyhedra in 3D [START_REF] Bronnimann | Lines and free line segments tangent to arbitrary three-dimensional convex polyhedra[END_REF].

Our study shows that standard procedures for solving these predicates have high degrees. We study, in particular, procedures that involve computing the Plücker coordinates of the line transversals involved in the predicates.

Computing lines through four lines

We describe here a method for computing the line transversals to four lines in real projective space P 3 (R). This method is a variant, suggested by Devillers and Hall-Holt [START_REF] Devillers | [END_REF] and also described in Redburn [START_REF] Redburn | Robust computation of the non-obstructed line segments tangent to four amongst n triangles[END_REF], of that by Hohmeyer and Teller [START_REF] Hohmeyer | Determining the lines through four lines[END_REF]; note that, for evaluating predicates, the latter method is not appropriate because it uses singular value decomposition for which we only know of numerical methods and thus the line transversals cannot be computed exactly, when needed.

Each line can be described using Plücker coordinates (see [START_REF] Shoemake | Plücker coordinate tutorial[END_REF], for example, for a review of Plücker coordinates). If a line ℓ in R 3 is represented by a direction vector u and a point p in R 3 then ℓ can be represented by the sixtuple ( u, u × -→ Op) in real projective space P 5 (R), where O is any arbitrarily, fixed, origin and × denote the cross product. The side product ⊙ of any two six-tuples ℓ = (a 1 , a 2 , a 3 , a 4 , a 5 , a 6 ) and k

= (x 1 , x 2 , x 3 , x 4 , x 5 , x 6 ) is ℓ ⊙ k = a 4 x 1 + a 5 x 2 + a 6 x 3 + a 1 x 4 + a 2 x 5 + a 3 x 6 .
The fundamental importance of the side product lies in the fact that a sixtuple k ∈ P 5 (R) represents a line in 3D if and only if k ⊙ k = 0; this defines a quadric in P 5 (R) called the Plücker quadric. More generally, recall that two lines intersect in real projective space P 3 (R) if and only if the side product of their Plücker coordinates is zero. Notice that this implies that there is a predicate for determining whether two lines intersect in P 3 (R) which is of degree two in the Plücker coordinates of the lines and, if the lines are each defined by two points, of degree three in the Cartesian coordinates of these points.

Oriented lines of R 3 , with direction vector u and through a point p, can be represented similarly by a six-tuple ( u, u × -→ Op) in real oriented projective space (i.e., the quotient of R 6 \ {0} by the equivalence relation induced by positive scaling). The sign (positive or negative) of the side operator of two oriented lines ℓ and k then determines on which "side" of ℓ, k lies; for instance, if op and oq are two lines oriented from o to p and from o to q and ℓ is an arbitrarily oriented line such that ℓ, p, q, and o are not coplanar, then (ℓ ⊙ op) (ℓ ⊙ oq) 0 if and only if ℓ intersects segment pq (see Figure 1(a)).

Given four lines ℓ 1 , . . . , ℓ 4 , our problem here is to compute all lines k = (x 1 , x 2 , x 3 , x 4 , x 5 , x 6 ) ∈ P 5 (R) such that k ⊙ ℓ i = 0, for 1 i 4, which can be written in the following form:

    a 4 a 5 a 6 a 1 a 2 a 3 b 4 b 5 b 6 b 1 b 2 b 3 c 4 c 5 c 6 c 1 c 2 c 3 d 4 d 5 d 6 d 1 d 2 d 3             x 1 x 2 x 3 x 4 x 5 x 6         =     0 0 0 0     (1)
where the rows of the 4 × 6 matrix contain the Plücker coordinates of the four lines. This can be rewritten as

    a 6 a 1 a 2 a 3 b 6 b 1 b 2 b 3 c 6 c 1 c 2 c 3 d 6 d 1 d 2 d 3         x 3 x 4 x 5 x 6     +     a 4 x 1 + a 5 x 2 b 4 x 1 + b 5 x 2 c 4 x 1 + c 5 x 2 d 4 x 1 + d 5 x 2     =     0 0 0 0     . (2)
Let δ denote the determinant of the above 4 × 4 matrix. Assuming δ = 0, we can solve the system for x 3 , x 4 , x 5 , and x 6 in terms of x 1 and x 2 . Applying Cramer's rule, we get

       x 3 = -(α 1 x 1 + β 1 x 2 )/δ x 4 = -(α 2 x 1 + β 2 x 2 )/δ x 5 = -(α 3 x 1 + β 3 x 2 )/δ x 6 = -(α 4 x 1 + β 4 x 2 )/δ
where α i (respectively β i ) is the determinant δ with the i th column replaced by (a 4 , b 4 , c 4 , d 4 ) T (respectively (a 5 , b 5 , c 5 , d 5 ) T ). We rewrite this system as

               x 1 = -u δ x 2 = -v δ x 3 = α 1 u + β 1 v x 4 = α 2 u + β 2 v x 5 = α 3 u + β 3 v x 6 = α 4 u + β 4 v (3) with (u, v) ∈ P 1 (R).
Since k is a line, we have k ⊙ k = 0, which implies

x 1 x 4 + x 2 x 5 + x 3 x 6 = 0.
Substituting in the expressions for x 1 . . . x 6 , we get

Au 2 + Buv +Cv 2 = 0 (4)
where

A = α 1 α 4 -α 2 δ, B = α 1 β 4 + β 1 α 4 -β 2 δ -α 3 δ, C = β 1 β 4 -β 3 δ.
Solving this degree-two equation in (u, v) and replacing in (3), we get (assuming that A = 0) that the Plücker coordinates of the transversal lines k are:

               x 1 = B δ ∓ δ √ B 2 -4 AC x 2 = -2 A δ x 3 = -B α 1 + 2 A β 1 ± α 1 √ B 2 -4 AC x 4 = -B α 2 + 2 A β 2 ± α 2 √ B 2 -4 AC x 5 = -B α 3 + 2 A β 3 ± α 3 √ B 2 -4 AC x 6 = -B α 4 + 2 A β 4 ± α 4 √ B 2 -4 AC.
(

) 5
Lemma 1. Consider four lines, given by the Cartesian coordinates of pairs of points, that admit finitely many line transversals in P 3 (R). If the four lines are not parallel to a common plane, the Plücker coordinates of their transversals in P 3 (R) can be written as

φ i + ϕ i √ ∆, i = 1, . . . , 6
, where φ i , ϕ i , and ∆ are polynomials of degree at most 17, 6, and 22, respectively, in the coordinates of the input points. Otherwise, the Plücker coordinates of the transversals can be written as polynomials of degree at most 19. Moreover, these bounds are, in the worst case, reached for three of the coordinates.

Proof. The assumption that the four lines admit finitely many transversals in P 3 (R) ensures that the 4 × 6 matrix of Plücker coordinates (in (1)) has rank 4. Consider first the case where the four input lines are not all parallel to a common plane. Then, the 4 × 3 matrix of the direction vectors of the four lines has rank 3. By the basis extension theorem, this matrix can be complemented by one of the other columns of the matrix of Plücker coordinates (of (1)) in order to get a 4 × 4 matrix of rank 4. We can thus assume, without loss of generality, that the 4 × 4 matrix of (2) has rank 4. Since, by assumption, the four lines admit finitely many transversals in P 3 (R), A, B, and C in (4) are not all zero. We compute the degree, in the coordinates of the input points, of the various polynomial terms in [START_REF]CGAL: Computational Geometry Algorithms Library[END_REF]. For each input line ℓ i , the first three and last three coordinates of its Plücker representation have degree 1 and 2, respectively. Hence δ, α 1 , and β 1 have degree 5 and α i and β i have degree 6 for i = 2, 3, 4. Hence, A, B, and C have degree 11 and the bounds on the degrees of φ i , ϕ i , and ∆ follow. Note, in particular, that, if A = 0, these bounds are reached for i = 4, 5, 6.

Consider now the case where the four input lines are parallel to a common plane. Since the four lines admit finitely many transversals in P 3 (R), they are not parallel. It follows that the 4 × 3 matrix of the direction vectors of the four lines has rank 2. Two vectors, say (a i , b i , c i , d i ) for i = 1, 2, are thus linearly independent and, by the basis extension theorem, the corresponding 4 × 2 matrix can be complemented by two other columns (say, (a i , b i , c i , d i ) for i = 4, 5) of the matrix of Plücker coordinates (of (1)) in order to define a 4 × 4 matrix of rank 4. As above, a straightforward computation gives the Plücker coordinates of the line transversal. We get

x 1 = α 1 u, x 2 = α 2 u, x 3 = -u δ, x 4 = α 3 u + β 3 v, x 5 = α 4 u + β 4 v, x 6 = -v δ where (u, v) ∈ P 1 (R) is solution of the equation A ′ u 2 + B ′ u v = 0 where A ′ = α 1 α 3 + α 2 α 4 and B ′ = α 1 β 3 + α 2 β 4 + δ 2 . (6)
δ, α 1 , α 2 , β 3 , β 4 have degree 6 and α 3 , α 4 have degree 7 (and β 1 = β 2 = 0) thus A ′ and B ′ have degree 13 and 12, respectively. Note that A ′ and B ′ are not both zero since there are finitely many transversals. The Plücker coordinates of the transversals can thus be written as polynomials of degree at most 19 and, for one of the transversals (the one not in the plane at infinity), this bound is reached for three coordinates (namely, x 4 , x 5 , x 6 ).

Lemma 2. Consider four lines, given by the Cartesian coordinates of pairs of points, that admit finitely many line transversals in P 3 (R). If the four lines are not parallel to a common plane, we can compute on each transversal two points whose homogeneous coordinates have the form

φ i + ϕ i √ ∆, i = 1, . . . , 4
, where φ i , ϕ i , and ∆ are polynomials of degree at most 17, 6, and 22, respectively, in the coordinates of the input points. Otherwise, we can compute on each transversal two points whose homogeneous coordinates are polynomials of degree at most 19. Moreover, these bounds are reached, in the worst case, for some coordinates.

Proof. Denote by w 1 (resp. w 2 ) the vector of the first (resp. last) three coordinates of (x 1 , . . . , x 6 ), the Plücker coordinates of a line k, and let n denote any vector of R 3 . Then, if the four-tuple (w 2 × n, w 1 • n) is not equal to (0, 0, 0, 0), it is a point (in homogeneous coordinates) on the line k (by Lagrange's triple product expansion formula). By considering the axis unit vectors for n, we get that the four-tuples (0, x 6 , -x 5 , x 1 ), (-x 6 , 0, x 4 , x 2 ), (x 5 , -x 4 , 0, x 3 ) that are non-zero are points on the transversal lines k. Either five of the six Plücker coordinates of k are zero or at least two of these four-tuples are non-zero and thus are points on k. In the latter case, the result follows from Lemma 1. In the former case, two points with coordinates 0 or 1 can easily be computed on line k since the line is then one of the axis or a line at infinity defined by the directions orthogonal to one of the axis.

Remark 3.

In some implementations (for instance, the one of [START_REF] Redburn | Robust computation of the non-obstructed line segments tangent to four amongst n triangles[END_REF]), the 4 × 4 submatrix of the matrix of Plücker coordinates (see [START_REF] Boissonnat | Robust plane sweep for intersecting segments[END_REF]) used for computing the line transversals is chosen, by default, as the leftmost submatrix whose determinant has degree 7 in the coordinates of the input points. In this case, the Plücker coordinates of the line transversals are written as

φ i + ϕ i √ ∆, i = 1, . . . , 6
, where φ i , ϕ i , and ∆ are polynomials of degree at most 20, 7, and 26, respectively, in the coordinates of the input points (and these bounds are reached). Similarly for the homogeneous coordinates of two points on the transversals.

Predicates

Preliminaries

We start by two straightforward lemmas on the degree of predicates for determining the sign of simple algebraic numbers. If x is a polynomial expression in some variables, we denote by deg(x) the degree of x in these variables. This first lemma is trivial and its proof is omitted.

Lemma 4. If a, b, and c are polynomial expressions of (input) rational numbers, the sign of a+b √ c can be determined by a predicate of degree

max{2 deg(a), 2 deg(b) + deg(c)}. Lemma 5. If α i , β i , δ, µ, i = 1, 2, are polynomial expressions of (input) rational numbers, the sign of α 1 + β 1 √ δ + (α 2 + β 2 √ δ) √ µ can be obtained by a predicate of degree max{4 deg(α 1 ), 4 deg(β 1 ) + 2 deg(δ), 4 deg(α 2 ) + 2 deg(µ), 4 deg(β 2 ) + 2 deg(δ) + 2 deg(µ), 2 deg(α 1 ) + 2 deg(β 1 ) + deg(δ), 2 deg(α 2 ) + 2 deg(β 2 ) + 2 deg(µ) + deg(δ)}.
Proof. The predicate is to evaluate the sign of an expression of the form a

+ b √ µ, where a = α 1 + β 1 √ δ, b = α 2 + β 2 √
δ, and α i , β i , µ, δ are rational. This can be done by evaluating the signs of a, b, and a 2b 2 µ. The first two signs can be obtained by directly applying Lemma 4. On the other hand,

a 2 -b 2 µ is equal to A + B √ δ with A = α 2 1 + β 2 1 δ -α 2 2 µ -β 2 2 µδ and B = 2α 1 β 1 -2α 2 β 2 µ. The sign of A + B √
δ can be determined by another application of Lemma 4, which gives the result.

Transversals to four lines

We consider first the predicate of determining whether four lines admit 0, 1, 2, or infinitely many line transversals in P 3 (R) (that is lines in P 3 (R) that intersect, in P 3 (R), the four input lines). An evaluation of this predicate directly follows from the algorithm described in Section 2 for computing the line transversals. Recall that, in the sequel, all input points are, by assumption, given by their Cartesian coordinates.

Theorem 6. Given four lines defined by pairs of points, there is a predicate of degree 22 in the coordinates of these points to determine whether the four lines admit 0, 1, 2, or infinitely many line transversals in P 3 (R).

Proof. We consider three cases. First, if the four lines are parallel, which can easily be determined by a predicate of degree 3, then they admit infinitely many line transversals in P 3 (R). Second, if the four lines are not parallel but parallel to a common plane, which can easily be determined by a predicate of degree 3, then the four lines admit infinitely many transversals if Equation ( 6) is identically zero and, otherwise, 2 line transversals in P 3 (R) ; this can thus be determined with a predicate of degree 13 (see the proof of Lemma 1). Finally, if the four lines are not parallel to a common plane, they admit infinitely many transversals if Equation 4 is identically zero and, otherwise, 0, 1, or 2 transversals depending on the sign of ∆ (in Lemma 1) which is of degree 22 in the coordinates of the points defining the lines.

Note that if the leftmost (instead of the rightmost) 4 × 4 submatrix of the matrix of Plücker coordinates (in (1)) is used for computing line transversals (see Remark 3) then the procedure described in the above proof has degree 26 instead of 22.

All line transversals are defined in R 3 except in the case where the four input lines are parallel to a common plane, in which case the intersection of this plane with the plane at infinity is a line transversal at infinity. Note also that, determining whether a line transversal in P 3 (R) is transversal in R 3 amounts to determining whether the transversal is parallel to one of the four input lines ℓ i , that is if their direction vectors are collinear. This can be done, by Lemmas 1 and 4, by a predicate of degree 36 in the Cartesian coordinates of the points defining the input lines.

Note, however, that if the points defining the ℓ i have rational coordinates and if the transversal is parallel to one of the ℓ i , the Plücker coordinates of the transversal are rational; indeed, the multiplicative factor of the direction vectors is rational (since one of the coordinates of the direction vector of the transversal is rational, e.g., x 2 in (5)) and thus all the coordinates of this direction vector are rational, which implies that ∆ is a square in [START_REF]CGAL: Computational Geometry Algorithms Library[END_REF]. Hence, deciding whether a transversal is parallel to one of the input lines ℓ i can be done by first determining whether ∆ is a square and, if so, testing whether the direction vectors are collinear. It thus follows from Lemma 1 that determining whether a transversal is parallel to one of the input lines ℓ i can be done with a fixed-precision floating-point arithmetic using a number of bits roughly equal to 22 times the number of bits used in representing each input value. This should be compared to the degree 36 of the above procedure. In this paper we have restricted our attention to evaluation procedures for predicates that consist entirely of determining the signs of polynomial expressions in the input parameters. We see here an example of a predicate which may be more effeciently evaluated by a procedure which permits other operations, in this case, dertermining whether a rational number is a square. This provides an interesting example of a geometric predicate whose algebraic degree does not seem to be an entirely adequate measure of the number of bits needed for the computation.

Transversals to four segments

We consider here the predicate of determining how many transversals four segments of R 3 admit. Recall that four segments may admit up to 4 or infinitely many line transversals [START_REF] Brönnimann | Transversals to line segments in threedimensional space[END_REF]. In this section, we prove the following theorem.

Theorem 7. Given four line segments, there is a predicate of degree 36 in the coordinates of their endpoints to determine whether those segments admit 0, 1, 2, 3, 4, or infinitely many line transversals.

Note that if, the leftmost (instead of the rightmost) 4 × 4 submatrix of the matrix of Plücker coordinates (in (1)) is used for computing line transversals (see Remark 3) then the procedure described below for the predicate of Theorem 7 has degree 42 instead of 36.

We consider, in the following, the supporting lines of the four segments, that is, the lines containing the segments; in the case where one (or several) segment is reduced to a point, we consider as supporting line, any line through this point and parallel to at least another supporting line. We first consider the case where the four supporting lines admit finitely many transversals in P 3 (R); this can be determined by a predicate of degree 22, by Theorem 6. Lemma 8. Given four segments in R 3 whose supporting lines admit finitely many line transversals in P 3 (R), determining the number of transversals to the four segments can be done with a predicate of degree 36 in the coordinates of their endpoints.

Proof. Let ℓ denote an (arbitrarily) oriented line, as well as its Plücker coordinates, that is transversals to the four lines; ℓ can be computed as described in Section 2. We consider the predicate of determining whether ℓ intersects each of the four segments, in turn. Let p and q denote the endpoints of one of these segments. For any two distinct points r and s, denote by rs the Plücker coordinates of the line rs oriented from r to s; depending on the context, rs also denotes the line through r and s or the segment from r to s.

If a point o does not lie in the plane containing line ℓ and segment pq (see Figure 1(a)), then line ℓ intersects segment pq if and only if the oriented line ℓ is on opposite sides of the two oriented lines from o to p and from o to q, that is if (ℓ ⊙ op) (ℓ ⊙ oq) 0 (recall that ⊙ denotes the side operator -see Section 2).

On the other hand, point o lies in a plane containing line ℓ and segment pq if and only if ℓ intersects (in P 3 (R)) both lines op and oq, that is both side operators ℓ ⊙ op and ℓ ⊙ oq are zero. By choosing point o to be for instance (1, 0, 0), (0, 1, 0), (0, 0, 1), or (1, 1, 1), we ensure that one of these points will not be coplanar with ℓ and segment pq unless segment pq lies on ℓ.

Hence the predicate follows from the sign of side operators of the line transversal and of a line defined by two points, one of which with coordinates equal to 0 or 1. The degree of the Plücker coordinates of the line through these two points is thus 1 (in the coordinates of the input points). Hence, by Lemma 1, the predicate can be computed by determining the sign of polynomials of degree at most 20 if the input lines are parallel to a common plane and, otherwise, by determining the sign of expressions of the form a + b √ c where a, b and c have degree at most 18, 7, and 22, respectively; moreover, these bounds are reached. By Lemma 4, the predicate thus has degree 36, which concludes the proof.

We now consider the case where the four lines admit infinitely many transversals. Recall that, in P 3 (R), four lines or line segments admit infinitely many transversals only if [START_REF] Brönnimann | Transversals to line segments in threedimensional space[END_REF]:

1. they lie in one ruling of a hyperbolic paraboloid or a hyperboloid of one sheet, 2. they are all concurrent, or 3. they all lie in a plane, with the possible exception of a group of one or more that all meet that plane at the same point.

We treat the cases independently.

Lemma 9. Given four segments in R 3 whose supporting lines are pairwise skew and admit infinitely many line transversals, determining the number of their line transversals can be done with a predicate of degree at most 36 in the coordinates of their endpoints.

Proof. When four lines are pairwise skew, their common transversals can be parameterized by their points of intersection with one of the lines; moreover, the set of common transversals to the four segments corresponds (through this parameterization) to up to four intervals on that line and the transversals that correspond to the endpoints of these intervals contain (at least) one endpoint of the segments [START_REF] Brönnimann | Transversals to line segments in threedimensional space[END_REF]. We can compute and order all these interval endpoints and determine whether there exists a transversal (to the four segments) through each midpoint of two consecutive distinct interval endpoints. By construction and by [START_REF] Brönnimann | Transversals to line segments in threedimensional space[END_REF], the four segments admit such a transversal if and only if they admit infinitely many transversals. The set of interval endpoints, on, say, segment s 1 is a subset of the endpoints of s 1 and of the intersection points of s 1 with the planes containing s 2 and an endpoint of s 3 or s 4 and of the intersection points of s 1 with the planes containing s 3 and an endpoint of s 2 . The coordinates of these points can be trivially computed as rational expressions of degree 4 in the coordinates of the segment endpoints. The coordinates of the midpoints are thus rational expressions of degree at most 8.

The transversal to the four lines through (any) one of these midpoints intersects line ℓ 2 and lies in the plane containing line ℓ 3 and the considered midpoint; the coordinates of the intersection point between this plane and ℓ 2 are rational expressions of degree at most 19. Finally, determining whether a transversal (to the four lines) through two points whose coordinates are rational expressions of degree 8 and 19 is a transversal to each of the four segments can be done, as in the proof of Lemma 8, using side operators. Hence, we can decide whether the four segments admit infinitely many transversals with a predicate of degree at most 36 since the Plücker coordinates of the line transversal are of degree at most 35. Now, if the four segments admit finitely many transversals, we can determine the number of transversals as follows. As mentioned above, the set of transversals can be parameterized by intervals on a line and the interval endpoints correspond to transversals that go through a segment endpoint. A transversal is isolated if and only if it corresponds to an interval that is reduced to a point. Thus, a transversal is isolated only if it goes through two distinct segment endpoints (the segments necessarily have distinct endpoints since, by assumption, their supporting lines are pairwise skew and thus no segment is reduced to a point). Determining whether the lines through two distinct endpoints intersect the other segments can easily be done, as described in the proof of Lemma 8, by computing the sign of side operators which are here of degree 3 in the coordinates of the segment endpoints.

Lemma 10. Given four segments in R 3 whose supporting lines are not pairwise skew and admit infinitely many line transversals, determining the number of their line transversals can be done with a predicate of degree 7 in the coordinates of their endpoints.

Proof. First, note that testing whether two segments intersect can be done using side operators with a predicate of degree 3. The four lines containing the segments are not pairwise skew and they admit infinitely many line transversals. Thus, they are all concurrent or they all lie in a plane H, with the possible exception of a group of one or more that all meet that plane at the same point [START_REF] Brönnimann | Transversals to line segments in threedimensional space[END_REF]. Four cases may occur:

(i) all four lines lie in a plane H, (ii) three lines lie in a plane H and the fourth line intersects H in exactly one point, (iii) two lines lie in a plane H and two other lines intersect H in exactly one and the same point, (iv) three lines are concurrent but not coplanar.

Differentiating between these cases can be done by determining whether sets of four segment endpoints are coplanar (which is a predicate of degree 3). We study each case in turn.

Case (i).

The four segments are coplanar. Any component of transversals contains a line through two distinct segment endpoints. Hence the four segments have finitely many transversals if and only if any line through two distinct endpoints that is a transversal to the four segments is an isolated transversal. This only occurs1 (see Figure 1(b)) when the transversal goes through the endpoints of three segments such that the segment, whose endpoint is in between the two others, lies (in H) on the opposite side of the transversal than the two other segments. This can be tested by computing the sign of scalar products and side operators between the transversal and the lines through a point o not in H and the segment endpoints (see Figure 1(b)). This leads to a predicate of degree 4.

Case (ii).

Three lines lie in a plane H. Testing whether the fourth segment intersects the plane H can easily be done by computing the point of intersection between H and the line containing the fourth segment, leading to a predicate of degree 3. If the fourth segment does not intersect plane H, the four segments have no transversal unless the first three segments are concurrent in which case the four segments have one or infinitely many transversals depending on whether the four lines supporting the segments are concurrent. Otherwise, let p denote the point of intersection. We assume that the three segments in H are not concurrent; otherwise the four segments have infinitely many transversals. Thus, any component of transversals contains a line through p and through a segment endpoint. Hence the four segments have finitely many transversals if and only if any line through p and a segment endpoint that is a transversal to the four segments is an isolated transversal. Testing whether such a line is a transversal to all segments can be done, as in the proof of Lemma 8, by computing the sign of side operators of the line transversal and of lines through a segment endpoint and a point o not in H; the coordinates of point p are rational expressions of degree 4, thus the Plücker coordinates of the transversal have degree at most 6, which leads to a predicate of degree 7. Such a line transversal is isolated (see Figure 1(c)) if and only if2 the transversal goes through two endpoints of two distinct segments that lie on the same side (in plane H) of the transversal or not depending whether p is in between the two endpoints or not. This test can be done by computing the sign of scalar products and side operators between the transversal and the lines through a point o not in H and the segment endpoints (see Figure 1(c)). This test also leads to a predicate of degree 7. We can thus determine the number of isolated transversals with a predicate of degree 7.

Case (iii).

Two lines lie in a plane H and two other lines intersect H in exactly one and the same point. (Note that there may be two instances of plane H for a given configuration.) This case can be treated similarly as Case (ii).

Case (iv). Three lines are concurrent but not coplanar. If none of the three corresponding segments intersect, they have no common transversal. If only two segments intersect, the three segments have exactly one transversal; checking whether that transversal intersects the fourth segment can easily be done with a predicate of degree 3. Now, if the three segments intersect, then the four segments have infinitely many transversals if they are concurrent or if their supporting lines are not concurrent. Otherwise, if the four segments are not concurrent but their supporting lines are, the four segments then have a unique transversal. This can also be checked with a predicate of degree 3.

We can now conclude the proof of Theorem 7. By Theorem 6, we can determine with a predicate of degree 22 whether the four lines containing the four segments admit finitely many transversals in P 3 (R). If the four lines admit finitely many transversals, then, by Lemma 8, determining the number of transversals to the four segments can be done with a predicate of degree 36. Assume now that the four lines admit infinitely many transversals. Note that determining whether the input lines are pairwise skew can easily be done with a predicate of degree 3. Thus, by Lemmas 9 and 10, determining whether the four segments admit 0, 1, 2, 3, 4, or infinitely many line transversals can be done by a predicate of degree at most 36. Hence, we can determine the number of transversals to four segments with a predicate of degree 36.

Transversals to four segments and a triangle

We consider here the predicate of determining whether a minimal segment transversal to four line segments is intersected by a triangle. Given a line transversal ℓ to a set S of segments, a triangle T occludes ℓ if ℓ intersects T and if there exist two segments in S whose intersections with ℓ lie on opposite sides of T . We describe a method for evaluating the predicate for determining whether a triangle occludes a transversal to a given set of line segments and establish its degree.

Theorem 11. Let ℓ be a line transversal to four line segments that admit finitely many transversals and let T be a triangle. There is a predicate of degree 78 in the coordinates of the points defining the segments and the triangle to determine whether T occludes ℓ.

Proof. Let ℓ denote an oriented line transversal to segments s 1 , . . . , s 4 , each defined by two points e i and f i , i = 1, . . . , 4, and let T be a triangle defined by three points p, q, and r. The Plücker coordinates of ℓ can be computed as described in Section 2. We only consider the case where the four lines containing segments s i have finitely many transversals because, otherwise, since the four segments admit finitely many transversals, each transversal goes through at least one endpoint of the four segments and it is straightforward that the degree of the predicate is then much smaller.

We first determine whether ℓ intersects T by taking the side product of ℓ with each supporting line of T (oriented consistently); ℓ intersects T if and only if no two side products have opposite signs (i.e., ±1). Similarly as in the proof of Lemma 8, there is a predicate of degree 38 for determining the sign of these side operators.

Assuming that ℓ intersects T , we next find the point of intersection. By Lemma 2, ℓ can be represented parametrically in the form π + ρt. We determine the value of t for which the determinant of p, q, r, π + ρt is equal to zero; denote this value of t by t 0 . This determinant has the form a 0 + b 0 t 0 , where, by Lemma 2, a 0 and b 0 are polynomials of degree 22 if s 1 , . . . , s 4 are parallel to a common plane or, otherwise, have the form φ + ϕ √ ∆ where φ, ϕ, and ∆ have degree 20, 9, and 22, respectively, in the coordinates of p, q, r, e i , f i . Now, for each segment s i , we compute the point of intersection of s i with ℓ in terms of the parameter t using the method similar to that of the previous section: choose a point o i not in the plane determined by s i and ℓ and compute the value t for which the determinant of e i , f i , o i , π + ρt equals 0. Denote this value by t i . Since o i can be chosen with all coordinates equal to 0 or 1, we get, similarly as in the previous paragraph, that each of these determinants has the form a i + b i t i where a i and b i are polynomials of degree 21 if s 1 , . . . , s 4 are parallel to a common plane or, otherwise, have the form φ + ϕ √ ∆ where φ, ϕ, and ∆ have degree 19, 8, and 22, respectively.

Determining whether T occludes ℓ is now only a matter of determining whether t 0 lies between two of the values t i , i = 1, . . . , 4, which requires only that we be able to compare t-values, that is, compute sign(t it j ). Observe that

t i -t j = a j b i -a i b j b i b j < 0, so sign(t i -t j ) = sign(a j b i -a i b j ) sign(b i ) sign(b j ).
It follows from the above characterization of the a i and b i that a product a i b j is either a polynomial of degree 43 if s 1 , . . . , s 4 are parallel to a common plane or, otherwise, has the form φ + ϕ √ ∆ where φ, ϕ, and ∆ have degree at most 39, 28, and 22, respectively (and these bounds are reached in the worst case). Applying Lemma 4 yields a predicate of degree 78, which concludes the proof.

Note that, if the leftmost (instead of the rightmost) 4 × 4 submatrix of the matrix of Plücker coordinates (in (1)) is used for computing line transversals (see Remark 3) then the procedure described above for the predicate of Theorem 11 has degree 90 instead of 78.

p 1 p 2 p 1 p 2 v 1 , v 2 P 0 P 1 P 2 v 1 , v 2 P 0 P 1 P 2 (b) (c) v 2 v 1 O ℓ P 2 P 1 P 0 (a)
Figure 2. Planes P 1 and P 2 such that P 1 < P 2

Ordering planes through two fixed points, each containing a third (rational) point or a line transversal

Let ℓ be a line defined by two points v 1 and v 2 , and ℓ be the line ℓ oriented in the direction --→ v 1 v 2 . We define an ordering of all the planes containing ℓ with respect to the oriented line ℓ and a reference point O (not on ℓ). Let P 0 be the plane containing O and ℓ, and let P 1 and P 2 be two planes containing ℓ. We say that P 1 < P 2 if and only if P 1 is encountered strictly before P 2 when rotating counterclockwise about ℓ a plane from P 0 (see Figure 2a).

Let p i be any point on plane P i but not on ℓ, for i = 1, 2, and let D(p, q) denote the determinant of the four points (v 1 , v 2 , p, q) given in homogeneous coordinates.

Lemma 12. With χ = D(O, p 1 ) • D(O, p 2 ) • D(p 1 , p 2 ), we have: (a) If χ > 0 then P 1 > P 2 . (b) If χ < 0 then P 1 < P 2 . (c) If χ = 0 then (i) if D(p 1 , p 2 ) = 0, then P 1 = P 2 , (ii) else if D(O, p 1 ) = 0, then P 1 < P 2 , (iii) else P 1 > P 2 .
Proof. Assume first that D(O, p 1 ) • D(O, p 2 ) > 0, that is, that p 1 and p 2 lie strictly on the same side of the plane P 0 (see Figure 2b). Then the order of P 1 and P 2 is determined by the orientation of the four points (v 2c). The order of P 1 and P 2 is then still determined by the sign of D(p 1 , p 2 ). However, P 1 > P 2 if and only if D(p 1 , p 2 ) < 0. Hence, we have in all cases that, if χ > 0, then P 1 > P 2 and, if χ < 0, then P 1 < P 2 .

Suppose finally that χ = 0. If D(p 1 , p 2 ) = 0, then p 1 and p 2 are coplanar, and P 1 = P 2 . Otherwise, if D(O, p 1 ) = 0, then P 0 = P 1 thus P 1 is smaller to all other planes (containing ℓ), and in particular P 1 P 2 . Furthermore, since D(p 1 , p 2 ) = 0, P 1 = P 2 and thus P 1 < P 2 . Otherwise, D(O, p 2 ) = 0 and we get similarly that P 2 < P 1 .

Computing a point on a plane defined by ℓ and a line transversal. We want to order planes P i that are defined by line ℓ and either a rational point not on ℓ, or by a line transversal to ℓ and three other lines. In the latter case, we consider a point on the line transversal (which is non-rational, in general; see Lemma 2). The following lemma tells us that, in general, such a plane P i contains no rational points outside of ℓ, and that in the cases where it does contain such a rational point, the line transversal is then rational. Hence, if the points computed on the line transversal, as described in Lemma 2, are not rational, there is no need to search for simpler points on the plane (but not on ℓ). The standard approach to comparing two such planes is to first evaluate the predicate using fixed-precision intervalarithmetic. This is very efficient but may fail when the sign of an expression cannot be successfully determined because the result of the evaluation of the expression is an interval that contains zero. If this happens, the answer to the predicate is then obtained by either evaluating exactly the expression (and thus its sign) using exact arithmetic or by increasing the precision of the interval arithmetic until either the result of the evaluation of the expression is an interval that does not contain zero or the separation bound is attained (see for instance [START_REF] Burnikel | A separation bound for real algebraic expressions[END_REF][START_REF] Mignotte | Identification of algebraic numbers[END_REF][START_REF] Scheinerman | When close enough is close enough[END_REF][START_REF] Yap | Towards exact geometric computation[END_REF]); in both approaches the computation is much slower than when using fixed-precision interval-arithmetic. We are thus interested in determining how often the fixed-precision interval-arithmetic evaluation of our predicate fails.

To test our predicate, we generate pairs of planes, each defined by two lines, one chosen at random and common to the two planes, and the other defined as a transversal to the common line and to three other random lines. We are interested in evaluating our predicate in the case where the two planes are very close together, that is, when there is significant risk of producing an error when using finite-precision floating-point arithmetic.

We generate two sets of four lines. Each line of the first set is determined by two points, all of whose coordinates are double-precision floating-point numbers chosen uniformly at random from the interval [-5000, 5000]. The second set of lines is obtained by perturbing the points defining three of the lines of the first set; the fourth line is not perturbed and is thus common to the two sets. To perturb a point p, we translate it to a point chosen uniformly at random in a sphere centered at p, with radius ε.

We compute, for each of these two sets of four lines, a line transversal. If either set of four lines does not admit a transversal (which happens roughly 24% of the time), we throw out that data and start again. Otherwise, we choose a transversal in a consistent way for the two sets of four lines, that is, such that one transversal converges to the other when ε tends to zero. Each transversal, together with the common line, defines a plane.

For various values of ε, varying from 10 -2 to 10 -10 , we evaluate the predicate using double-precision floatingpoint interval arithmetic until we obtain 1000 pairs of planes for which the computation of the predicate fails. We measure the percentage of time that the computation fails. The results of these experiments are shown in Table 1.

We observe, as expected, that when ε is sufficiently small (10 -10 ), that is, when the two planes are often close enough to each other, the fixed-precision interval-arithmetic predicate fails with high probability and that this probability decreases as ε increases. When ε = 10 -2 , the probability of failure is close to zero. Finally, we have also observed that the predicate fails when the angle between the two planes is less than roughly 10 -8 radians, which is, of course, independent of ε.

Note finally that the percentage of failure of the degree 168 predicate using fixed-precision interval-arithmetic is, as expected, high compared to lower-degree predicates. Table 1 also shows the failure rate for the degree 3 predicate related to Theorem 14(i). We use the same experimental scheme as above, that is, we chose at random three points that define a plane and perturb one of these points by at most ε.

All the experiments were made on a i686 machine with AMD Athlon 1.73 GHz CPU and 1 GB of main memory using the CGAL interval number type with double-precision floating-point numbers [START_REF]CGAL: Computational Geometry Algorithms Library[END_REF].

Figure 1 .

 1 Figure 1. (a): Transversal ℓ intersects segment pq only if (ℓ ⊙ op) (ℓ ⊙ oq) 0. (b-c): An illustration for the proof of Lemma 10.

Table 1 .

 1 Percentages of failure of the degree 168 and degree 3 predicates using double-precision floating-point interval-arithmetic, for ε varying from 10 -12 to 10 -2 .

	P P P P P P P P predicates ε	10 -12 10 -10	10 -8	10 -6	10 -4	10 -2
	degree 168	99.6% 50.4% 7.6%	0.8%	0.08% 0.008%
	degree 3	99.5% 8.2% 0.08% 0.001%

For simplicity, we do not discuss here the case where the line transversal contains one of the four segments.

We assume here for simplicity that the line transversal contains no segment.

Acknowledgment

The authors gratefully acknowledge fruitful discussions on this topic with Olivier Devillers and Marc Glisse. We also especially thank Hervé Brönnimann for his comments on the paper and Günter Rote for pointing out an improvement, in Lemma 1, to the degrees appearing in the Plücker coordinates of line transversals.

This research was carried out while this author was visiting LORIA and partially funded by the INRIA associated team ISA-McGill.

Lemma 13. The plane P containing a rational line ℓ and a line transversal to ℓ and three other segments, each determined by two rational points, contains in general no rational points except on ℓ. Furthermore, if plane P contains a rational point not on ℓ then the line transversal is rational.

Proof. Suppose that the plane P contains a rational point p not on ℓ. Then the plane contains three (non-collinear) rational points, p and two points on ℓ, and thus P is a rational plane. This plane intersects the three other segments in three points, all of which are rational and lie on the transversal. So the transversal is a rational line which implies that the discriminant B 2 -4 AC in Equation ( 5) is a square, which is not the case in general.

Comparing two planes. We want to order planes P i that are defined by either line ℓ and another (input rational) point not on ℓ, or by line ℓ and a line transversal to ℓ and three other lines.

By Lemma 12, ordering such planes about ℓ amounts to computing the sign of determinants of four points (in homogeneous coordinates). Two of these points are input (affine rational) points on ℓ (v 1 and v 2 ) and each of the two other points is either an input (affine rational) point r i , i = 1, 2, or is, by Lemma 2 (and Lemma 13), a point u i whose homogeneous coordinates have degree at most 19 (in the coordinates of the input points) or a point of the form

, where the ∆ i have degree 22 and where the p i and q i are points with homogeneous coordinates of degree at most 17 and 6, respectively. If the four points are all input points, then the determinant of the four points has degree 3 in their coordinates.

If only three of the four points are input points, then the determinant of the four points is either a polynomial of degree 22 or it has the form D(p 1 , r 1 ) + D(q 1 , r 1 ) √ ∆ 1 where the degrees of the D() are 20 and 9, respectively, in the coordinates of the input points. Hence, by Lemma 4, the sign of this expression can be determined with a predicate of degree 40.

Finally, if only two of the four points are input points, then the determinant has one of the following forms (depending on whether the quadruples of lines defining the transversals are parallel to a common plane); the degrees are given in terms of the coordinates of the input points:

(i) D(u 1 , u 2 ) which is of degree 40.

(ii) D(u 1 , p 1 ) + D(u 1 , q 2 ) √ ∆ 1 where the D() have degree 38 and 27, respectively.

where the D() have degree 36, 25, 25, and 14, respectively.

Hence, by Lemma 5, the sign of these expressions can be determined with a predicate of degree at most 144 (and the bound is reached in the worst case). We thus get the following result.

Theorem 14. Let ℓ be an oriented line defined by two points, let p 0 be a point not on ℓ, and let P 0 be the plane determined by ℓ and p 0 . Given two planes P 1 , P 2 containing ℓ there is a predicate which determines the relative order of P 1 and P 2 about ℓ with respect to P 0 having the following degree in the coordinates of the input points:

Experiments

In this section, we report the results of experiments that analyze the behavior of the predicate for ordering, in a rotational sweep about a line, two planes each defined by a line transversal to four lines, that is the predicate related to Theorem 14(iii). The degree of the procedure we use for evaluating this predicate is 168 because we use for computing line transversals to four lines the code of Redburn [START_REF] Redburn | Robust computation of the non-obstructed line segments tangent to four amongst n triangles[END_REF], which, as noted in Remarks 3 and 15, leads to degree 168 instead of 144 as in Theorem 14(iii).


Candide Bidossessi Sindedji

Mathieu Dakle

Rodolphe Gueret

Laure Fort

Latifou Lagnika

Solange Imelda Avosse

Faridath Bouraima

Yves Gimbert

Teko W Napporn

Dodzi Zigah

Agnès Aubouy

Emmanuel Maisonhaute

Voltammetric techniques for low-cost on-site routine analysis of thymol in the medicinal plant Ocimum Gratissimum

Keywords: electrochemistry, essential oils, Ocimum gratissimum, thymol, chemical composition variation. Highlights Ocimum gratissimum GC: glassy carbon SWV: square wave voltammetry

published or not. The documents may come

Voltammetric techniques for low-cost on-site routine analysis of thymol in the medicinal plant Ocimum gratissimum

Latifou Lagnika, Solange Imelda Avosse, Faridath Oyélékan Bouraima,

Introduction

Alternative treatments compared to occidental pharmaceuticals often rely on the use of essential oils [START_REF] Matera | Plant essential oils as healthy functional ingredients of nutraceuticals and diet supplements: A Review[END_REF].

These are important in developing countries where traditional medicine is still the main source of health care and for which access to treatments at reasonable cost may be difficult as reported by the World Health Organization [START_REF]WHO traditional medicine strategy[END_REF]. A key issue for herbal health is the quality of the product in terms of chemical composition, safety and efficacy. Quality control of herbal health products is a critical challenge for its promotion and integration into health systems. One of the main difficulties is the variation in the chemical composition of plants due to genetic, agricultural and environmental factors (seasonal and climatic variations, soil composition), as well as in the process of collection, drying, storage and extraction that further influence the content of plant materials [START_REF] Conforti | The influence of collection zone on glucosinolates, polyphenols and flavonoids contents and biological profiles of Capparis sicula ssp. sicula[END_REF][START_REF] Camara | Variation in chemical composition and antimalarial activities of two samples of Terminalia albida collected from separate sites in Guinea[END_REF][START_REF] Czechowski | Detailed phytochemical analysis of high-and low artemisinin-producing chemotypes of Artemisia annua[END_REF][START_REF] Wani | Enhancing artemisinin content in and delivery from Artemisia annua: a review of alternative, classical, and transgenic approaches[END_REF]. Therefore, ideally, the amount of active components present in an herbal health product such as herbal tea or essential oil should be indicated and should be above a certain efficacy threshold. Typically, mass spectrometry approaches are used to decipher composition variations. Those provide excellent quantification and exhaustivity of all products [START_REF] Lebanov | Random Forests machine learning applied to gas chromatography -Mass spectrometry derived average mass spectrum data sets for classification and characterisation of essential oils[END_REF][START_REF] Mith | Chemical composition and antimicrobial activity of essential oils of Ocimum basilicum, Ocimum canum and Ocimum gratissimum in function of harvesting time[END_REF][START_REF] Kpadonou Kpoviessi | Chemical variation of essential oil constituents of Ocimum gratissimum L. from Benin, and impact on antimicrobial properties and toxicity against Artemia salina leach[END_REF]. Nevertheless, this heavy and expensive instrumentation requires specific training to be used properly. As a consequence, their use is restricted to specific research purposes and limited to a few samples per system. Hence, there is an avenue to propose alternative ways of quantifying the active molecules in those complex mixtures. More specifically, many plants contain antioxidants that are useful to fight oxidative stress and reduce the risk of many non-communicable diseases such as cardiovascular pathologies, cancers, atherosclerosis, diabetes, Alzheimer's disease, cataracts, and other respiratory disorders [START_REF] Da Veiga Correia | An integrative review on the main flavonoids found in some species of the Myrtaceae family: phytochemical characterization, health benefits and development of products[END_REF][START_REF] Kähkönen | Antioxidant activity of plant extracts containing phenolic compounds[END_REF]. Therefore, those systems are often possibly oxidized at an electrode surface, even in aqueous media.

While the most accurate methods for analyzing those complex media remain mass spectrometry [START_REF] Jalali-Heravi | Recent trends in application of multivariate curve resolution approaches for improving gas chromatography-mass spectrometry analysis of essential oils[END_REF], access to lightweight and low-cost instruments that can be directly deployed on-site would be of great interest. In this area, electrochemical methods appear very attractive and adapted [START_REF] Compton | Understanding Voltammetry[END_REF]. Indeed, potentiostats can be miniaturized and easily transported and powered by batteries (often from a laptop) [START_REF] Matsubara | A small yet complete framework for a potentiostat, galvanostat, and electrochemical impedance spectrometer[END_REF][START_REF] Ainla | Open-source potentiostat for wireless electrochemical detection with smartphones[END_REF][START_REF] Caux | PassStat, a simple but fast, precise and versatile open source potentiostat[END_REF][START_REF] Mercer | Glucose biosensor based on opensource wireless microfluidic potentiostat[END_REF]. Sophisticated electrode preparation procedures may be necessary if sub-µM concentrations of organic molecules need to be detected, but conventional electrodes are easily sensitive to concentrations in the sub-millimolar range without modification [START_REF] Wang | Analytical Electrochemistry[END_REF]. In addition, very cheap potentiostat configurations are nowadays proposed through open access instrumentation [START_REF] Caux | PassStat, a simple but fast, precise and versatile open source potentiostat[END_REF].

Below, we will explore how low-cost electrochemical analysis can be used to monitor the concentration of an active ingredient in an essential oil and an infusion. We choose the example of Ocimum gratissimum (OG) that grows and is frequently consumed in several parts of Benin. The leaves and roots are widely used traditionally in cooking, in medicinal recipes against fungal, urinary, infections, gonorrhea, bronchitis, vertigo, diarrhea, vomiting, respiratory, cardiovascular and liver diseases, fever and malaria, and as an insecticide [START_REF] Sessou | Comparative study of antifungal activities of six selected essential oils against fungal isolates from cheese wagashi in Benin[END_REF][START_REF] Fanou | Ethnobotanical survey on plants used in the treatment of candidiasis in traditional markets of southern Benin[END_REF][START_REF] Dougnon | Toxicological characterization of ten medicinal plants of the Beninese flora used in the traditional treatment of diarrheal diseases[END_REF][START_REF] Sam-Wobo | Comparative repellent activities of some plant extracts against Simulium damnosum complex[END_REF][START_REF] Ugbogu | A review on the traditional uses, phytochemistry, and pharmacological activities of clove basil (Ocimum gratissimum L.)[END_REF]. OG contains thymol, a phenol derivative that can be oxidized chemically or electrochemically and is biologically active [START_REF] Nagoor Meeran | Pharmacological properties and molecular mechanisms of thymol: prospects for its therapeutic potential and pharmaceutical development[END_REF][START_REF] Tonello | Square wave voltammetry with multivariate calibration tools for determination of eugenol, carvacrol and thymol in honey[END_REF][START_REF] Arteaga | Comparison of the simple cyclic voltammetry (CV) and DPPH assays for the determination of antioxidant capacity of active principles[END_REF][START_REF] Costentin | The electrochemical approach to concerted proton-electron transfers in the oxidation of phenols in water[END_REF][START_REF] Costentin | Evidence for concerted proton-electron transfer in the electrochemical oxidation of phenols with water as proton acceptor. Tri-tert-butylphenol[END_REF][START_REF] Venu | Oxidation reactions of thymol: a pulse radiolysis and theoretical study[END_REF]. In order to simplify the analytical procedure, we used only unmodified electrodes. Since thymol produces oligomers upon oxidation, we first examined the thymol electrochemical behavior in a first electrolyte (acidic conditions) to evaluate the optimal concentration range where sensitivity is sufficient but electrode passivation, that induces a departure from linearity, avoided. Then, quantification of thymol in two OG essential oils was performed and compared with independent mass spectrometry and IR measurements. Subsequently, the conditions were optimized to carry out direct measurements in an aqueous infusion made directly from the plant leaves. In order to propose a full electrochemical setup at a reduced cost, in a final study we considered the use of pencil leads to perform the detection.

Material and methods

Electrochemical experiments were performed at the Laboratory of Biochemistry and Bioactive Natural Substances, Faculté des Sciences et Technique of Université d'Abomey-Calavi. Therefore, experimental procedures were adapted to the local conditions.

Products. Sulfuric acid (VWR, 95-98%), Citric acid (Aldrich, 99.5%), Sodium chloride (VWR, 99.9%), absolute ethanol (Aldrich,> 99.8%) and Thymol (Aldrich, 98.5%) were used as received. We realized that distilled water was not pure enough so that we resorted to the local mineral water Fifa whose composition is provided in supporting information. One advantage is that mineral water only contains electroinactive ions and that its composition is verified and public anywhere on the planet. Electrolyte was either a 50/50 volumetric mixture of 0.5 M sulfuric acid and ethanol, or an aqueous solution containing 0.1 M NaCl and 0.1 M citric acid.

The leaves of OG were collected in their natural habitat in the township of Abomey-Calavi, department of the Atlantic, agroecological zone n°6, southern Benin for sample 1 and in the township of Djougou, agroecological zone n°4, northern Benin for sample 2. For essential oil extraction, the leaves were first dried for several days. Then, 100 g of collected material in each township and 500 mL of distilled water were introduced in 1 L flask and fixed onto the hydrodistillation Clevenger apparatus system. Each extraction was performed continuously for 2-3 hours. The essential oil was collected into an amber bottle protected from light by aluminum foil. For the infusion, the fresh leaves of OG were collected in an organic garden in the township of Sèmè-Podji, agroecological zone n°8, southern Benin. Infusions were prepared by adding 250 mL of boiling mineral water to 25 g of OG leaves. We observed that it is important to close the recipient otherwise thymol can escape with vapours.

Potentiostat and electrochemical cell. We resorted to the open source potentiostat PassStat 2.1 recently reported by some of us, and which costs ca 50€ [START_REF] Caux | PassStat, a simple but fast, precise and versatile open source potentiostat[END_REF]. Briefly, this potentiostat is powered and controlled by the USB port of a laptop. In Benin, the 50 Hz electrical grid is not always stable and contains many parasites, which introduces significant noise into the measurements. To face that issue, we carried out the measurements without connecting the laptop to the mains. In addition, the potentiostat and electrochemical cell were placed in a home-made Faraday cage made with aluminum foil connected to the ground of the potentiostat. The current/voltage conversion resistance R6 of the potentiostat was manually adjusted to fit the measured current, as well as the capacitance CF3 that filters the noise. Taking the same notations as in our previous work [START_REF] Caux | PassStat, a simple but fast, precise and versatile open source potentiostat[END_REF], typical values for a 2 mm diameter working electrode are R6 = 100 k, and CF3 = 10 nF. The frugal electrochemical cell was made in a glass yogurt container with holes in the cap to insert the electrodes. No inert gas was available so that experiments were performed under atmospheric environment and at room temperature (27  3°C). Pictures of the set-up are provided in Figure 1. Oxygen reduction wave was used to assess that the electrode was not passivated. We alternatively used an Emstat Pico from Palmsens to compare our results with a commercial system. No noticeable difference was found.

OG solutions were prepared by adding 100 µL of OG essential in a 10 mL volumeter flask that was then filled with pure ethanol. Then, aliquots were added to a 50 mL electrolyte solution. For calibration, a 25 mM solution of thymol in the electrolyte was prepared.

Electrodes. Working electrodes were either a 2 mm diameter glassy carbon electrode from Origalys or a 3.15 mm diameter 6B pencil lead from Faber Castell. Electrodes were hand polished with P4000 paper and then 0.3 µm alumina excepted for the pencil lead for which only P4000 was used. Then, the electrode was sonicated for 2 min in pure mineral water. We observed an important dependence of the voltammogram shape and peak currents on the surface state of the electrode. Three assays were performed by sample and two groups performed independent calibration and measurements with different potentiostats and electrodes, but identical OG oil and electrolytes. Thus, electrodes were polished after each voltammogram, and datas presenting obvious fouling of the electrode even after polishing were discarded. A baseline subtraction was performed to evaluate the faradaic peak currents.

Counter electrode was a 0.5 mm diameter platinum wire or a pencil lead. Reference electrode was either a commercial (CHI) or a home-made AgCl/Ag reference electrode.

Mass spectrometry

Gas Chromatography -Mass Spectrometry was performed on an Agilent 5977A-7890B system with electronic impact. Acquisitions were performed in the single ion monitoring mode. The capillary GC column was a HP-5MS.

Results and discussion

Thymol electrochemical reactivity

Since the extraction of essential oils is made by hydrodistillation, the products obtained are often very poorly soluble in water. Therefore, we first used a 50/50 volumetric mixture of 0.5 M sulfuric acid/ethanol to prepare our electrolyte. Acidic solutions were chosen because the electroxidation peaks of phenol derivatives are larger and well-defined under these conditions. Figure 2 presents the cyclic voltammogram obtained for a 149 µM of thymol on a glassy carbon electrode at 0.1 V s -1 . A chemically irreversible peak is observed at 0.97 V vs AgCl/Ag. On the backward scan, a small wave is detected at 0.12 V vs AgCl/Ag. This wave is chemically reversible as observed on the second scan which presents a peak at 0.49 V vs AgCl/Ag. The precise nature of the products formed is unknown, but it is wellknown that thymol and other phenol derivatives produce oligomers or polymers that are easier to oxidize upon a 1 electron 1 proton oxidation [START_REF] Costentin | The electrochemical approach to concerted proton-electron transfers in the oxidation of phenols in water[END_REF][START_REF] Costentin | Evidence for concerted proton-electron transfer in the electrochemical oxidation of phenols with water as proton acceptor. Tri-tert-butylphenol[END_REF][START_REF] Taouil | How protein structure affects redox reactivity: example of Human centrin 2[END_REF]. These polyphenolic systems are logically easier to oxidize than their parent thymol. As a consequence of electrode passivation, at the second and successive cycles, the peak shape is smoothed and the current diminished. The inset of Figure 2 shows the corrected peak current (subtracted from a linear baseline) of the first cycle as a function of thymol concentration.

It is observed that above 200 µM, the linearity is lost because electropolymerization and electrode passivation are already effective, resulting in a peak potential shift and lower peak current. Within a concentration range between 50 and 200 µM, we estimate that the peak current allows to estimate the thymol concentration with a 10% error. A precise evaluation of the detection threshold was however not performed since in our case we handle rather large concentrations. In the literature, it is well-established that carvacrol, a regioisomer of thymol, presents similar electrochemical characteristics. Nevertheless, since it has been shown that carvacrol is only a minor product in the oil produced in Benin, we did not consider a full electrochemical characterization of this compound [START_REF] Mith | Chemical composition and antimicrobial activity of essential oils of Ocimum basilicum, Ocimum canum and Ocimum gratissimum in function of harvesting time[END_REF][START_REF] Kpadonou Kpoviessi | Chemical variation of essential oil constituents of Ocimum gratissimum L. from Benin, and impact on antimicrobial properties and toxicity against Artemia salina leach[END_REF]. Since electrode passivation is strongly dependent on the initial solution composition of the solution, but also on the surface state and thus on the polishing, it seemed risky to work beyond the linear range even if one study reports electropolymerization to discriminate between thymol and carvacrol that present oxidation at identical potentials [START_REF] Bertuola | Detection of carvacrol in essential oils by electrochemical polymerization[END_REF]. Therefore, in the next section, we diluted the OG oil in order to stay in the appropriate concentration range and similarly checked the linearity range of the electrochemical response.

Quantification of thymol content in OG essential oils

The chemical composition of medicinal plants and more specifically OG can vary depending on several factors such as the climate, area and time of harvest, soil parameters and phenology of plants [START_REF] Mith | Chemical composition and antimicrobial activity of essential oils of Ocimum basilicum, Ocimum canum and Ocimum gratissimum in function of harvesting time[END_REF][START_REF] Kpadonou Kpoviessi | Chemical variation of essential oil constituents of Ocimum gratissimum L. from Benin, and impact on antimicrobial properties and toxicity against Artemia salina leach[END_REF]. For example, the essential oil of OG leaves harvested in Brazil is rich in Eugenol and Eucalyptol [START_REF] Melo | Chemical composition and antimicrobial effectiveness of Ocimum gratissimum L. essential oil against multidrug-resistant isolates of Staphylococcus aureus and Escherichia coli[END_REF] while those harvested in Benin are rich in Thymol, p-cymene and γ-terpinene [START_REF] Atrevy | Efficacy of some essential oils in the fight against strains of mould extracted from smoked fish taken in South Benin[END_REF]. In Benin, Kpadonou et al.

showed that two chemotypes have been observed depending on the time of harvest: p-cymene/thymol chemotype for plants harvested at 7 a.m. and p-cymene chemotype for those harvested at 1 p.m. or 7 p.m. [START_REF] Kpadonou Kpoviessi | Chemical variation of essential oil constituents of Ocimum gratissimum L. from Benin, and impact on antimicrobial properties and toxicity against Artemia salina leach[END_REF]. In the present study, leaves of O. gratissimum were harvested in two agro-ecological areas which differ in climate, soil type and rainfall. We collected one sample from the township of Abomey-Calavi (sample 1, southern Benin) and one from the township of Djogou (sample 2, northern Benin) to illustrate the geographic variability and the potential of electrochemistry as a simple discrimination method. Each oil was diluted 100 times in ethanol and aliquots were added to 50 mL of electrolyte. CVs were then acquired as in the previous section. Figure 3a shows the results obtained for OG-sample 1. It is clear that the curves exhibit similarities with those presented in the previous section, which suggests that their shape is determined by the thymol content of the oil. As in the previous section, we checked the linearity of the response for sample 1 and determined that below 400 µL the peak current could be used to determine the OG concentration. The average of all measurements yielded a thymol concentration of 25  5 mM in the diluted sample 1, therefore 2.5  0.5 M in the pure oil. Reproducibility was checked and another operator found 2.7  0.5 M. Thus, the accuracy is highly sufficient to determine the thymol concentration in OG essential oil. In order to get further information on this striking difference between the two samples, a quantification of thymol and carvacrol content in our samples was performed by gas chromatographymass spectrometry. We found 2.34 M for sample 1 (2.20 M thymol + 0.15 M carvacrol) and 6.2×10 -3 M (3.1×10 -3 thymol and 3.1×10 -3 M carvacrol) for 2, as detailed in Supporting Information, in very good agreement with our electrochemical measurements. These first results demonstrate that cyclic voltammetry and classical electrochemical setups without extensive sample or electrode preparation are already sufficient to discriminate between plant extracts that contain significant amounts of thymol or not.

Electrochemistry within an infusion

After obtaining the probing results mentioned above, we decided to shift our focus to the analysis of an infusion. After preparing the infusion, we added 0.1 M citric acid + 0.1 M NaCl as electrolyte, as these inexpensive products can be easily obtained. We observed with this new electrolyte a positive effect, i.e. electrode fouling by oligomers was reduced under these conditions, extending the linearity range to higher concentrations. This could be due to hydrogen bonding between OH groups of thymol derivatives and citric acid. However, we had to dilute the initial solution five times with pure electrolyte to stay in the linear range. Figure 4a presents the CV obtained for the system. A large chemically reversible peak is observed at 0.554 V vs AgCl/Ag. This peak is induced by the soluble antioxidant species such as flavonoids, tannins, phenolic compounds or glycosides [START_REF] Arteaga | Comparison of the simple cyclic voltammetry (CV) and DPPH assays for the determination of antioxidant capacity of active principles[END_REF][START_REF] Prabhu | Ocimum gratissimum: A review of its chemical, pharmacological and ethnomedicinal properties[END_REF][START_REF] Olumide | Comparative study of proximate, mineral and phytochemical analysis of the leaves of Ocimum gratissimum, Vernonia amygdalina and Moringa oleifera[END_REF]. The second small peak is attributed to thymol, as previously identified. In this study, we also resorted to square wave voltammetry (SWV, see Figure 4b), that is known to be more sensitive and can better distinguish species when peaks overlap [START_REF] Compton | Understanding Voltammetry[END_REF]. We tested here the sample addition method and observed a linear behavior up to the addition of 3 mL of 25 mM thymol into 50 mL of electrolyte. SWV yielded a thymol concentration of 550  85 µM in the final solution (thus 2.8  0.5 mM in the initial one).

Low-cost electrochemical cell

In a final attempt to minimize all costs, we replaced the glassy carbon working electrode and the platinum counter electrode with pencil leads. In fact, pencil leads are made of graphite and a polymer to ensure cohesion [START_REF] Bernalte | Pencil It in: Exploring the Feasibility of Hand-Drawn Pencil Electrochemical Sensors and Their Direct Comparison to Screen-Printed Electrodes[END_REF]. In the literature, such electrodes are emerging for several electroanalytical purposes [START_REF] Annu | Review-Pencil graphite electrode: an emerging sensing material[END_REF], and have been used for the evaluation of antioxidants in tea [START_REF] Vishnu | Tea quality testing using 6B pencil lead as an electrochemical sensor[END_REF], for the titration of eugenol (another phenol derivative) [START_REF] Sağlam | Differential pulse voltammetric determination of eugenol at a pencil graphite electrode[END_REF] and for the determination of copper in sea water after electrode modification with a specific complexing molecule [START_REF] Challier | An ultrasensitive and highly selective nanomolar electrochemical sensor based on an electrocatalytic peak shift analysis approach for copper trace detection in water[END_REF] among other examples. Different ratios graphite/polymer are available, and we chose 3.15 mm diameter 6B pencil leads insulated with epoxy resin since they present a high graphite load but are still mechanically resistant. Figure 5 presents three CVs obtained after the introduction of a freshly polished electrode in the precedent solution, and the results of the current evolution for the sample addition method (1 and 2 mL were added to 50 mL of solution). We determined a concentration of 580  85 µM of thymol with the pencil lead (2.9  0.5 mM in the initial infusion) for the same solution than in the previous section. Nevertheless, we have to point out that we have also noticed that the thymol wave increases with time whereas the one of antioxidants remains rather constant so that we present here results obtained after keeping the electrode 5 min in the solution prior starting the voltammetric acquisition. This indicates that for these electrodes, thymol adsorption contributes to the current which can then be larger than expected. In fact, adsorption results in higher current density, which may be an advantage and be exploited in the future to detect lower concentrations. However, it is also a source of irreproducibility. Further work will be performed in the future to propose an accurate methodology for complex mixtures containing systems that adsorb to the pencil lead electrodes, possibly by introducing a pre-anodization of the electrode [START_REF] Vishnu | A preanodized 6B-pencil graphite as an efficient electrochemical sensor for mono-phenolic preservatives (phenol and meta-cresol) in insulin formulations[END_REF]. Otherwise, using a cylindrical pencil lead electrode as a counter electrode was not problematic and even provided a larger counter electrode. Since we used a home-made AgCl/Ag reference electrode, the total price of the electrochemical cell is less than 5 €.

Conclusion

Overall, our work illustrates how analytical electrochemistry can be implemented in non-ideal experimental environment. The electrochemistry of thymol is challenging due to oligomerization, which partially blocks the electrode surface and requires the experimentalist to polish the electrode after each voltammogram. Nevertheless, we have successfully determined that peak current proportionality with concentration is valid in micromolar solutions, enabling quantification in a sulfuric acid/ethanol mixture that can be probably of interest for quantification of other substances poorly soluble in water. We could easily ascertain that OG sample from Abomey-Calavi contains a rather large quantity of thymol whereas none was detected in the sample from Djougou. This is an important finding in view of future biological activity tests. Furthermore, using only water but citric acid and sodium chloride as electrolyte, thus cheap and worldwide available compounds was found to provide excellent quantification of thymol in infusions. These measurements were performed with a low-cost electrochemical apparatus. Pencil lead electrodes and home-made reference electrodes may also be used to minimize the cost. Future improvements may involve optimization of electrode preparation or adjusting the voltammetric scan rate. A slight increase in the scan rate may prevent oligomerization while keeping a low capacitive background that is typical for carbon electrode and without introducing limitations due to electron transfer kinetics. This study demonstrates that electrochemistry may be implemented at a low cost for both teaching and research purposes, while still keeping performances close to those shown by commercial systems. More particularly, this technique is highly relevant for the determination of concentrations of active molecules in complex mixtures such as essential oils or herbal teas, for the further development of quality control of plant-based health products.

Figure 1 .

 1 Figure 1. Picture of the low-cost electrochemical setup.

Figure 2 .

 2 Figure 2. Cyclic voltammogram of glassy carbon electrode in 50/50 0.5 M sulfuric acid/ethanol solution containing 149 µM thymol recorded with a commercial potentiostat at 0.1 V s -1 . Inset: evolution of the peak current of the first cycle with thymol concentration c (black dots). I(µA) = 0.043c(µM).

Figure

  Figure 3b presents the cyclic voltammograms after the addition of 200 µL of OG-sample1 or 1400 µL of OG-sample 2. Although a clear signal is observed for sample 1, nothing is visible for sample 2.

Figure 3 .

 3 Figure 3. Cyclic voltammograms obtained on a glassy carbon electrode after different additions of OGsample 1 and OG-sample 2, previously diluted 100 times in ethanol, to 50 mL of electrolyte. Data were recorded with the open source potentiostat PassStat 2.1 at 0.1 V s -1 : a) CV of OG-sample 1 after addition

Figure 4 .

 4 Figure 4. a) Cyclic voltammogram of a glassy carbon electrode recorded in OG infusion + 0.1 M citric acid + 0.1 M NaCl solution recorded with an Open source PassStat 2.1 potentiostat at 0.1 Vs -1 ; b) Square wave voltammograms of glassy carbon electrode in electrolyte solution (50 mL) + addition of 0 mL (black), 1mL (red), 2 mL (blue) and 3 mL (pink) of 25 mM thymol standards; Inset: peak current I vs standard addition volume V. I(µA) = 1.24 + 1.12V(mL).

Figure 5 .

 5 Figure 5. Cyclic voltammograms of a 3.15 mm diameter 6B pencil lead electrode recorded in OG infusion + 0.1 M citric acid + 0.1 M NaCl electrolyte recorded with an Open source PassStat 2.1 potentiostat at 0.1 V s -1 after addition of 0 mL (black), 1 mL (red) or 2 mL (blue) of 5 mM thymol standard to 50 mL of electrolyte. Inset: peak current I vs standard addition volume V. I(µA) = 7.31 + 6.33V(mL).

Acknowledgements

This work was funded by Sorbonne Université, the Université de Poitiers, the Institut de Recherche pour le Développement and the CNRS through the Mission pour les Initiatives Transverses et l'Interdisciplinarité (project ELABORE).