Connected components of real algebraic sets are semi-algebraic sets, i.e. they are described by a boolean formula whose atoms are polynomial constraints with real coefficients. Computing such descriptions finds topical applications in optical system design and robotics. In this paper, we design a new algorithm for computing such semi-algebraic descriptions for real algebraic curves. Notably, its complexity is less than the best known one for computing a graph which is isotopic to the real space curve under study.

We consider linear matrix inequalities (LMIs) A = A0 + x1A1 + ⋅⋅⋅ + xnAn⪰0 with the Ai’s being m × m symmetric matrices, with entries in a ring \(\mathcal {R}\). When \(\mathcal {R}= \mathbb {R}\), the feasibility problem consists in deciding whether the xi’s can be instantiated to obtain a positive semi-definite matrix. When \(\mathcal {R}= \mathbb {Q}[y_1, \ldots , y_t]\), the problem asks for a formula on the parameters y1, …, yt, which describes the values of the parameters for which the specialized LMI is feasible. This problem can be solved using general quantifier elimination algorithms, with a complexity that is exponential in n. In this work, we leverage the LMI structure of the problem to design an algorithm that computes a formula Φ describing a dense subset of the feasible region of parameters, under genericity assumptions. The complexity of this algorithm is exponential in n, m and t but becomes polynomial in n when m and t are fixed. We apply the algorithm to a parametric sum-of-squares problem and to the convergence analyses of certain first-order optimization methods, which are both known to be equivalent to the feasibility of certain parametric LMIs, hence demonstrating its practical interest.

We consider systems of polynomial equations and inequalities in <?TeX $\mathbb {Q}[ \boldsymbol {y}][\boldsymbol {x}]$?> Math 1 where x = (x1, …, xn) and y = (y1, …, yt). The y indeterminates are considered as parameters and we assume that when specialising them generically, the set of common complex solutions, to the obtained equations, is finite.

International audience

Local minima are a well-known drawback of image-based visual servoing systems. Up to now, there were no formal guarantees on their number, or even their existence, according to the considered configuration. In this work, a formal approach is presented for the exhaustive computation of all minima and unstable equilibria for a class of six well-known image-based visual servoing controllers. This approach relies on a new polynomial formulation of the equilibrium condition that avoids using the camera pose. By using modern computational algebraic geometry methods and an ad hoc symmetry breaking strategy, the formal resolution of this new equilibrium condition is rendered computationally feasible. The proposed methodology is applied to compute the equilibria of several classical visual servoing tasks, with planar and nonplanar configurations of four and five points. The effects of local minima and saddle points on the dynamics of the system are finally illustrated through intensive simulation results, as well as the effects of image noise and uncertainties on depths.

Discrete Differential Equations (DDEs) are functional equations that relate algebraically a power series F(t, u) in t with polynomial coefficients in a “catalytic” variable u and the specializations, say at u = 1, of F(t, u) and of some of its partial derivatives in u. If a DDE is of a fixed-point type then its solution F(t, u) is unique, and an elegant result by Bousquet-Mélou and Jehanne implies that F(t, u) is an algebraic power series. Last year, Bostan et al. initiated a systematic algorithmic study of DDEs of order 1. We generalize this study to DDEs of arbitrary order. First, we propose nontrivial extensions of algorithms based on polynomial elimination and on the guess-and-prove paradigm. Second, we design two brand-new algorithms that exploit the special structure of the underlying polynomial systems. Last, but not least, we report on implementations that are able to solve highly challenging DDEs with a combinatorial origin.

We describe a recursive algorithm that decomposes an algebraic set into locally closed equidimensional sets, i.e. sets which each have irreducible components of the same dimension. At the core of this algorithm, we combine ideas from the theory of triangular sets, a.k.a. regular chains, with Gröbner bases to encode and work with locally closed algebraic sets. Equipped with this, our algorithm avoids projections of the algebraic sets that are decomposed and certain genericity assumptions frequently made when decomposing polynomial systems, such as assumptions about Noether position. Thus our algorithm has a chance to produce fine decompositions on more structured systems where ensuring genericity assumptions often prohibits exploiting the structure of the system at hand. Practical experiments demonstrate its efficiency compared to state-of-the-art implementations.

We consider the problem of computing a grevlex Gröbner basis for the set Fr(M) of minors of size r of an n × n matrix M of generic linear forms over a field of characteristic zero or large enough. Such sets are not regular sequences; in fact, the ideal ⟨Fr(M)⟩ cannot be generated by a regular sequence. As such, when using the general-purpose algorithm F5 to find the sought Gröbner basis, some computing time is wasted on reductions to zero. We use known results about the first syzygy module of Fr(M) to refine the F5 algorithm in order to detect more reductions to zero. In practice, our approach avoids a significant number of reductions to zero. In particular, in the case r = n − 2, we prove that our new algorithm avoids all reductions to zero, and we provide a corresponding complexity analysis which improves upon the previously known estimates.

In this paper, we consider the problem of deciding the existence of real solutions to a system of polynomial equations having real coefficients, and which are invariant under the action of the symmetric group. We construct and analyze a Monte Carlo probabilistic algorithm which solves this problem, under some regularity assumptions on the input, by taking advantage of the symmetry invariance property.

Solving zero-dimensional polynomial systems using Gröbner bases is usually done by, first, computing a Gröbner basis for the degree reverse lexicographic order, and next computing the lexicographic Gröbner basis with a change of order algorithm. Currently, the change of order now takes a significant part of the whole solving time for many generic instances. Like the fastest known change of order algorithms, this work focuses on the situation where the ideal defined by the system satisfies natural properties which can be recovered in generic coordinates. First, the ideal has a shape lexicographic Gröbner basis. Second, the set of leading terms with respect to the degree reverse lexicographic order has a stability property; in particular, the multiplication matrix can be read on the input Gröbner basis. The current fastest algorithms rely on the sparsity of this matrix. Actually, this sparsity is a consequence of an algebraic structure, which can be exploited to represent the matrix concisely as a univariate polynomial matrix. We show that the Hermite normal form of that matrix yields the sought lexicographic Gröbner basis, under assumptions which cover the shape position case. Under some mild assumption implying n≤t, the arithmetic complexity of our algorithm is O~(tω-1D), where n is the number of variables, t is a sparsity indicator of the aforementioned matrix, D is the degree of the zero-dimensional ideal under consideration, and ω is the exponent of matrix multiplication. This improves upon both state-of-the-art complexity bounds O~(tD2) and O~(Dω, since ω<3 and t≤D. Practical experiments, based on the libraries msolve and PML, confirm the high practical benefit.

Discrete differential equations of order 1 relate polynomially a power series F(t,u) in t with polynomial coefficients in a ''catalytic'' variable~u and one of its specializations, say F(t,u). Such equations are ubiquitous in combinatorics, notably in the enumeration of maps and walks. When the solution F is unique, a celebrated result by Bousquet-Mélou and Jehanne, reminiscent of Popescu's theorem in commutative algebra, states that F is algebraic. We address algorithmic and complexity questions related to this result. In generic situations, we first revisit and analyze known algorithms, based either on polynomial elimination or on the guess-and-prove paradigm. We then design two new algorithms: the first has a geometric flavor, the second blends elimination and guess-and-prove. In the general case (no genericity assumptions), we prove that the total arithmetic size of the algebraic equations for $F(t,1)$ is bounded polynomially in the size of the input discrete differential equation, and that one can compute such equations in polynomial time.

Cuspidal robots are robots with at least two inverse kinematic solutions that can be connected by a singularity-free path. Deciding the cuspidality of generic 3R robots has been studied in the past, but extending the study to six-degree-of-freedom robots can be a challenging problem. Many robots can be modeled as a polynomial map together with a real algebraic set so that the notion of cuspidality can be extended to these data.

Certifying the positivity of trigonometric polynomials is of first importance for design problems in discrete-time signal processing. It is well known from the Riesz-Fejér spectral factorization theorem that any trigonometric univariate polynomial non-negative on the unit circle can be decomposed as a Hermitian square with complex coefficients. Here we focus on the case of polynomials with Gaussian integer coefficients, i.e., with real and imaginary parts being integers.

We present a new open source C library msolve dedicated to solving multivariate polynomial systems of dimension zero through computer algebra methods. The core algorithmic framework of msolve relies on Gröbner bases and linear algebra based algorithms for polynomial system solving. It relies on Gröbner basis computation w.r.t. the degree reverse lexicographical order, Gröbner conversion to a lexicographical Gröbner basis and real solving of univariate polynomials. We explain in detail how these three main steps of the solving process are implemented, how we exploit AVX2 instruction processors and the more general implementation ideas we put into practice to better exploit the computational capabilities of this algorithmic framework. We compare the practical performances of msolve with leading computer algebra systems such as Magma, Maple, Singular on a wide range of systems with finitely many complex solutions, showing that msolve can tackle systems which were out of reach by the computer algebra software state-of-the-art.

Let V be the set of real common solutions to F = (f1, …, fs) in ℜ[x1, …;, xn] and D be the maximum total degree of the fi's. We design an algorithm which on input F computes the dimension of V. Letting L be the evaluation complexity of F and s=1, it runs using O∼ (L D n(d+3)+1) arithmetic operations in 𝒬 and at most Dn(d+1) isolations of real roots of polynomials of degree at most Dn.

Quantifier elimination over the reals is a central problem in computational real algebraic geometry, polynomial system solving and symbolic computation. Given a semi-algebraic formula (whose atoms are polynomial constraints) with quantifiers on some variables, it consists in computing a logically equivalent formula involving only unquantified variables. When there is no alternation of quantifiers, one has a one block quantifier elimination problem.

Given symmetric matrices A0,A1,…,An of size m with rational entries, the set of real vectors x=(x1,…,xn) such that the matrix A0+x1A1+⋯+xnAn has non-negative eigenvalues is called a spectrahedron. Minimization of linear functions over spectrahedra is called semidefinite programming. Such problems appear frequently in control theory and real algebra, especially in the context of nonnegativity certificates for multivariate polynomials based on sums of squares. Numerical software for semidefinite programming are mostly based on interior point methods, assuming non-degeneracy properties such as the existence of an interior point in the spectrahedron. In this paper, we design an exact algorithm based on symbolic homotopy for solving semidefinite programs without assumptions on the feasible set, and we analyze its complexity. Because of the exactness of the output, it cannot compete with numerical routines in practice. However, we prove that solving such problems can be done in polynomial time if either n or m is fixed.

Answering connectivity queries in semi-algebraic sets is a longstanding and challenging computational issue with applications in robotics, in particular for the analysis of kinematic singularities. One task there is to compute the number of connected components of the complementary of the singularities of the kinematic map. Another task is to design a continuous path joining two given points lying in the same connected component of such a set. In this paper, we push forward the current capabilities of computer algebra to obtain computer-aided proofs of the analysis of the kinematic singularities of various robots used in industry.

Let R be the field of real numbers. We consider the problem of computing the real isolated points of a real algebraic set in Rn given as the vanishing set of a polynomial system. This problem plays an important role for studying rigidity properties of mechanism in material designs. In this paper, we design an algorithm which solves this problem. It is based on the computations of critical points as well as roadmaps for answering connectivity queries in real algebraic sets. This leads to a probabilistic algorithm of complexity (nd)O (n log(n)) for computing the real isolated points of real algebraic hypersurfaces of degree d. It allows us to solve in practice instances which are out of reach of the state-of-the-art.

Let S\subset \bR^n be a compact basic semi-algebraic set defined as the real solution set of multivariate polynomial inequalities with rational coefficients. We design an algorithm which takes as input a polynomial system defining S and an integer p\geq 0 and returns the n-dimensional volume of S at absolute precision 2^-p . Our algorithm relies on the relationship between volumes of semi-algebraic sets and periods of rational integrals. It makes use of algorithms computing the Picard-Fuchs differential equation of appropriate periods, properties of critical points, and high-precision numerical integration of differential equations. The algorithm runs in essentially linear time with respect to~p. This improves upon the previous exponential bounds obtained by Monte-Carlo or moment-based methods. Assuming a conjecture of Dimca, the arithmetic cost of the algebraic subroutines for computing Picard-Fuchs equations and critical points is singly exponential in n and polynomial in the maximum degree of the input.

Let f= (f1, ..., fs) be a sequence of polynomials in Q[X1,...,Xn] of maximal degree D and V⊂ Cn be the algebraic set defined by f and r be its dimension. The real radical re < f > associated to f is the largest ideal which defines the real trace of V . When V is smooth, we show that re < f >, has a finite set of generators with degrees bounded by V. Moreover, we present a probabilistic algorithm of complexity (snDn )O(1) to compute the minimal primes of re < f >. When V is not smooth, we give a probabilistic algorithm of complexity sO(1) (nD)O(nr2r) to compute rational parametrizations for all irreducible components of the real algebraic set V ∩ Rn. Experiments are given to show the efficiency of our approaches.

We consider the problem of finding exact sums of squares (SOS) decompositions for certain classes of non-negative multivariate polynomials, relying on semidefinite programming (SDP) solvers. We start by providing a hybrid numeric-symbolic algorithm computing exact rational SOS decompositions for polynomials lying in the interior of the SOS cone. It computes an approximate SOS decomposition for a perturbation of the input polynomial with an arbitrary-precision SDP solver. An exact SOS decomposition is obtained thanks to the perturbation terms. We prove that bit complexity estimates on output size and runtime are both polynomial in the degree of the input polynomial and simply exponential in the number of variables. Next, we apply this algorithm to compute exact Polya and Putinar's representations respectively for positive definite forms and positive polynomials over basic compact semi-algebraic sets. We also compare the implementation of our algorithms with existing methods in computer algebra including cylindrical algebraic decomposition and critical point method.

Let R be a real closed field. We consider basic semi-algebraic sets defined by n -variate equations/inequalities of s symmetric polynomials and an equivariant family of polynomials, all of them of degree bounded by 2d < n. Such a semi-algebraic set is invariant by the action of the symmetric group. We show that such a set is either empty or it contains a point with at most 2d-1 distinct coordinates. Combining this geometric result with efficient algorithms for real root finding (based on the critical point method), one can decide the emptiness of basic semi-algebraic sets defined by s polynomials of degree d in time (sn)O(d). This improves the state-of-the-art which is exponential in n . When the variables x1, łdots, xn are quantified and the coefficients of the input system depend on parameters y1, łdots, yt, one also demonstrates that the corresponding one-block quantifier elimination problem can be solved in time (sn)O(dt).

A roadmap for a semi-algebraic setSis a curve which has a non-empty and connected intersection with all connected components ofS. Hence, this kind of object, introduced by Canny, can be used to answer connectivity queries (with applications, for instance, to motion planning) but has also become of central importance in effective real algebraic geometry, since it is used in higher-level algorithms. In this article, we provide a probabilistic algorithm which computes roadmaps for smooth and bounded real algebraic sets. Its output size and running time are polynomial in (nD)nlog (d), whereDis the maximum of the degrees of the input polynomials,dis the dimension of the set under consideration andnis the number of variables. More precisely, the running time of the algorithm is essentially subquadratic in the output size. Even under our assumptions, it is the first roadmap algorithm with output size and running time polynomial in (nD)nlog (d).

Control theory has recently been involved in the field of nuclear magnetic resonance imagery. The goal is to control the magnetic field optimally in order to improve the contrast between two biological matters on the pictures.

Let V ⊂ Cn be an equidimensional algebraic set and g be an n-variate polynomial with rational coefficients. Computing the critical points of the map that evaluates g at the points of V is a cornerstone of several algorithms in real algebraic geometry and optimization. Under the assumption that the critical locus is finite and that the projective closure of V is smooth, we provide sharp upper bounds on the degree of the critical locus which depend only on deg(g) and the degrees of the generic polar varieties associated to V. Hence, in some special cases where the degrees of the generic polar varieties do not reach the worst-case bounds, this implies that the number of critical points of the evaluation map of g is less than the currently known degree bounds. We show that, given a lifting fiber of V, a slight variant of an algorithm due to Bank, Giusti, Heintz, Lecerf, Matera and Solerno computes these critical points in time which is quadratic in this bound up to logarithmic factors, linear in the complexity of evaluating the input system and polynomial in the number of variables and the maximum degree of the input polynomials.

Let fΕ Q[X1, …, Xn] be a polynomial of degree D. We consider the problem of computing the real dimension of the real algebraic set defined by f=0. Such a problem can be reduced to quantifier elimination. Hence it can be tackled with Cylindrical Algebraic Decomposition within a complexity that is doubly exponential in the number of variables. More recently, denoting by d the dimension of the real algebraic set under study, deterministic algorithms running in time DO(d(n-d)) have been proposed. However, no implementation reflecting this complexity gain has been obtained and the constant in the exponent remains unspecified.

We consider the problem of optimizing a parametric linear function over a non-compact real trace of an algebraic set. Our goal is to compute a representing polynomial which defines a hypersurface containing the graph of the optimal value function. Rostalski and Sturmfels showed that when the algebraic set is irreducible and smooth with a compact real trace, then the least degree representing polynomial is given by the defining polynomial of the irreducible hypersurface dual to the projective closure of the algebraic set.

Let H0, …, H n be m x m matrices with entries in Q and Hankel structure, i.e. constant skew diagonals. We consider the linear Hankel matrix H(x) = H0+x1H_1+…+xnHn and the problem of computing sample points in each connected component of the real algebraic set defined by the rank constraint rank}(H(x))≤ r, for a given integer r ≤ m-1. Computing sample points in real algebraic sets defined by rank defects in linear matrices is a general problem that finds applications in many areas such as control theory, computational geometry, optimization, etc. Moreover, Hankel matrices appear in many areas of engineering sciences. Also, since Hankel matrices are symmetric, any algorithmic development for this problem can be seen as a first step towards a dedicated exact algorithm for solving semi-definite programming problems, i.e. linear matrix inequalities. Under some genericity assumptions on the input (such as smoothness of an incidence variety), we design a probabilistic algorithm for tackling this problem. It is an adaptation of the so-called critical point method that takes advantage of the special structure of the problem. Its complexity reflects this: it is essentially quadratic in specific degree bounds on an incidence variety. We report on practical experiments and analyze how the algorithm takes advantage of this special structure. A first implementation outperforms existing implementations for computing sample points in general real algebraic sets: it tackles examples that are out of reach of the state-of-the-art.

Let V ∈ Q(i)(a1,..., an)(q1, q2) be a rationally parametrized planar homogeneous potential of homogeneity degree k ≠ −2, 0, 2. We design an algorithm that computes polynomial necessary conditions on the parameters (a1,..., an) such that the dynamical system associated to the potential V is integrable. These conditions originate from those of the Morales-Ramis-Simó integrability criterion near all Darboux points. The implementation of the algorithm allows to treat applications that were out of reach before, for instance concerning the non-integrability of polynomial potentials up to degree 9. Another striking application is the first complete proof of the non-integrability of the collinear three body problem.

No abstract available.

Let K be a field and (f1, ..., fn)\subset K[X1, ..., Xn] be a sequence of quasi-homogeneous polynomials of respective weighted degrees (d1, ..., dn) w.r.t a system of weights (w1,...,wn). Such systems are likely to arise from a lot of applications, including physics or cryptography.

Consider a (D x D) symmetric matrix A whose entries are linear forms in Q[X1, ..., Xk] with coefficients of bit size ≤ τ. We provide an algorithm which decides the existence of rational solutions to the linear matrix inequality A ≥ 0 and outputs such a rational solution if it exists. This problem is of first importance: it can be used to compute algebraic certificates of positivity for multivariate polynomials. Our algorithm runs within (k≤)O(1)2O(min(k, D)D2)DO(D2) bit operations; the bit size of the output solution is dominated by τO(1)2O(\min(k, D)D2). These results are obtained by designing algorithmic variants of constructions introduced by Klep and Schweighofer. This leads to the best complexity bounds for deciding the existence of sums of squares with rational coefficients of a given polynomial. We have implemented the algorithm; it has been able to tackle Scheiderer's example of a multivariate polynomial that is a sum of squares over the reals but not over the rationals; providing the first computer validation of this counter-example to Sturmfels' conjecture.

We consider the problem of computing critical points of the restriction of a polynomial map to an algebraic variety. This is of first importance since the global minimum of such a map is reached at a critical point. Thus, these points appear naturally in non-convex polynomial optimization which occurs in a wide range of scientific applications (control theory, chemistry, economics,...).

International audience

Computing loci of rank defects of linear matrices (also called the MinRank problem) is a fundamental NP-hard problem of linear algebra which has applications in Cryptology, in Error Correcting Codes and in Geometry. Given a square linear matrix (i.e. a matrix whose entries are k-variate linear forms) of size n and an integer r, the problem is to find points such that the evaluation of the matrix has rank less than r+1. The aim of the paper is to obtain the most efficient algorithm to solve this problem. To this end, we give the theoretical and practical complexity of computing Gröbner bases of two algebraic formulations of the MinRank problem. Both modelings lead to structured algebraic systems. The first modeling, proposed by Kipnis and Shamir generates bihomogeneous equations of bi-degree (1,1). The second one is classically obtained by the vanishing of the (r+1)-minors of the given

Let X = [X1, ..., Xn] and f ∈ R[X]. We consider the problem of computing the global infimum of f when f is bounded below. For A ∈ GLn(C), we denote by fA the polynomial f(A X). Fix a number M ∈ R greater than infx∈Rn f(x). We prove that there exists a Zariski-closed subset A [equation] GLn(C) such that for all A ∈ GLn(Q) \ A, we have fA ≥ 0 on Rn if and only if for all ε > 0, there exist sums of squares of polynomials s and t in R[X] and polynomials [Equation]. Hence we can formulate the original optimization problems as semidefinite programs which can be solved efficiently in Matlab. Some numerical experiments are given. We also discuss how to exploit the sparsity of SDP problems to overcome the ill-conditionedness of SDP problems when the infimum is not attained.

We study a variant of the real quantifier elimination problem (QE). The variant problem requires the input to satisfy a certain extra condition, and allows the ouput to be almost equivalent to the input. In a sense, we are strengthening the pre-condition and weakening the post-condition of the standard QE problem.

Let f be a polynomial in Q[X1, ..., Xn] of degree D. We provide an efficient algorithm in practice to compute the global supremum supx∈ Rn f(x) of f (or its infimum inf{x∈ Rn}f(x)). The complexity of our method is bounded by DO(n)}. In a probabilistic model, a more precise result yields a complexity bounded by O(n7D4n) arithmetic operations in Q. Our implementation is more efficient by several orders of magnitude than previous ones based on quantifier elimination. Sometimes, it can tackle problems that numerical techniques do not reach. Our algorithm is based on the computation of generalized critical values of the mapping x-> f(x), i.e. the set of points {c∈ C mid exists (xll)ll∈ N}⊂ Cn ;f(xll)-> c, ;||xll||||dxll f||-> 0 { when }ll-> ∞}. We prove that the global optimum of f lies in its set of generalized critical values and provide an efficient way of deciding which value is the global optimum.

Classifying the Perspective-Three-Point problem (abbreviated by P3P in the sequel) consists in determining the number of possible positions of a camera with respect to the apparent position of three points. In the case where the three points form an isosceles triangle, we give a full classification of the P3P. This leads to consider a polynomial system of polynomial equations and inequalities with 4 parameters which is generically zero-dimensional. In the present situation, the parameters represent the apparent position of the three points so that solving the problem means determining all the possible numbers of real solutions with respect to the parameters' values and give a sample point for each of these possible numbers. One way for solving such systems consists first in computing a discriminant variety. Then, one has to compute at least one point in each connected component of its real complementary in the parameter's space. The last step consists in specializing the parameters appearing in the initial system by these sample points. Many computational tools may be used for implementing such a general method, starting with the well known Cylindrical Algebraic Decomposition (CAD in short), which provides more information than required. In a first stage, we propose a full algorithm based on the straightforward use of some sophisticated software such as FGb (Grobner bases computations) RS (real roots of zero-dimensional systems), DV (Discriminant varieties) and RAGlib (Critical point methods for semi-algebraic systems). We then improve the global algorithm by refining the required computable mathematical objects and related algorithms and finally provide the classification. Three full days of computation were necessary to get this classification which is obtained from more than 40000 points in the parameter's space.

We give a complete description of the Voronoi diagram of three lines in R3. 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.

Colloque avec actes et comité de lecture. internationale.