We study the problem of computing the L₁-distance between two piecewise-linear bivariate functions f and g, defined over a bounded polygonal domain 𝕄 ⊂ ℝ², that is, computing the quantity ‖f-g‖₁ = ∫_𝕄 |f(x,y)-g(x,y)| dx dy. If f and g are defined by linear interpolation over triangulations 𝐓_f and 𝐓_g, respectively, of 𝕄 with a total of n triangles, we show that ‖f-g‖₁ can be computed in Õ(n^α) time, where α = max{(ω+1)/2, 8/5}, ω is the matrix multiplication exponent, and Õ notation hides factors of the form n^ε for any ε > 0. This bound holds for the currently best known value of ω, which is approximately 2.37. More generally, if the complexity of the overlay of 𝐓_f and 𝐓_g is κ, then the runtime of our algorithm is Õ(κ^{α-1}n^{2-α}).

Evaluating or finding the roots of a polynomial f(z) = f0 + ⋅⋅⋅ + fdzd with floating-point number coefficients is a ubiquitous problem. By using a piecewise approximation of f obtained with a careful use of the Newton polygon of f, we improve state-of-the-art upper bounds on the number of operations to evaluate and find the roots of a polynomial. In particular, if the coefficients of f are given with m significant bits, we provide for the first time an algorithm that finds all the roots of f with a relative condition number lower than 2m, using a number of bit operations quasi-linear in the bit-size of the floating-point representation of f. Notably, our new approach handles efficiently polynomials with coefficients ranging from 2− d to 2d, both in theory and in practice.

We address the problem of computing a drawing of high resolution of a plane curve defined by a bivariate polynomial equation P(x,y)=0. Given a grid of fixed resolution, a drawing is a subset of pixels. Our goal is to compute an approximate drawing that (i) contains all the parts of the curve that intersect the pixel edges, (ii) excludes a pixel when the evaluation of P with interval arithmetic on each of its four edges is far from zero.

We present a new data structure to approximate accurately and efficiently a polynomial$f$of degree$d$given as a list of coefficients fi. Its properties allow us to improve the state-of-the-art bounds on the bit complexity for the problems of root isolation and approximate multi-point evaluation. This data structure also leads to a new geometric criterion to detect ill-conditioned polynomials, implying notably that the standard condition number of the zeros of a polynomial is at least exponential in the number of roots of modulus less than 1/2 or greater than 2. Given a polynomial$f$of degree$d$with ║f║1= Σ | fi| ≤ 2τfor τ ≥ 1, isolating all its complex roots or evaluating it at$d$points can be done with a quasi-linear number of arithmetic operations. However, considering the bit complexity, the state-of-the-art algorithms require at least d3/2bit operations even for well-conditioned polynomials and when the accuracy required is low. Given a positive integer$m$, we can compute our new data structure and evaluate$f$at$d$points in the unit disk with an absolute error less than 2−min Õ(d(τ + m)) bit operations, where Õ(.) means that we omit logarithmic factors. We also show that if κ is the absolute condition number of the zeros of f, then we can isolate all the roots of$f$in Õ(d(τ + log κ)) bit operations. Moreover, our algorithms are simple to implement. For approximating the complex roots of a polynomial, we implemented a small prototype in Python/NumPy that is an order of magnitude faster than the state-of-the-art solver MPSolve for high degree polynomials with random coefficients.

Let P and Q be two polynomials in K[x,y] with degree at most d, where K is a field. Denoting by R ∈ K[x] the resultant of P and Q with respect to y, we present an algorithm to compute R mod xk in O~(kd) arithmetic operations in K, where the ~O notation indicates that we omit polylogarithmic factors. This is an improvement over state-of-the-art algorithms that require to compute R in O~(d3) operations before computing its first k coefficients.

We consider the problem of computing the distance between two piecewise-linear bivariate functions f and g defined over a common domain M , induced by the L 2 norm—that is, ‖ f - g ‖2 = √∫ M ( f - g ) 2 . If f is defined by linear interpolation over a triangulation of M with n triangles and g is defined over another such triangulation, the obvious naive algorithm requires Θ( n 2 ) arithmetic operations to compute this distance. We show that it is possible to compute it in O ( n log 4 n log log n ) arithmetic operations by reducing the problem to multipoint evaluation of a certain type of polynomials. We also present several generalizations and an application to terrain matching.

We address the problem of computing a linear separating form of a system of two bivariate polynomials with integer coefficients, that is a linear combination of the variables that takes different values when evaluated at the distinct solutions of the system. The computation of such linear forms is at the core of most algorithms that solve algebraic systems by computing rational parameterizations of the solutions and this is the bottleneck of these algorithms in terms of worst-case bit complexity. We present for this problem a new algorithm of worst-case bit complexity ÕB(d7 + d6τ) where d and τ denote respectively the maximum degree and bitsize of the input (and where Õ refers to the complexity where polylogarithmic factors are omitted and OB refers to the bit complexity). This algorithm simplifies and decreases by a factor d the worst-case bit complexity presented for this problem by Bouzidi et al. [5]. This algorithm also yields, for this problem, a probabilistic Las-Vegas algorithm of expected bit complexity ÕB(d5 + d4τ).

We consider the problem of computing the distance between two piecewise-linear bivariate functions f and g defined over a common domain M. We focus on the distance induced by the L2-norm, that is . If f is defined by linear interpolation over a triangulation of M with n triangles, while g is defined over another such triangulation, the obvious naïve algorithm requires Θ(n2) arithmetic operations to compute this distance. We show that it is possible to compute it in O(n log n) arithmetic operations, by reducing the problem to multi-point evaluation of a certain type of polynomials. We also present an application to terrain matching.

Parallel robots admit generally several solutions to the direct kinematics problem. The aspects are associated with the maximal singularity free domains without any singular configurations. Inside these regions, some trajectories are possible between two solutions of the direct kinematic problem without meeting any type of singularity: non-singular assembly mode trajectories. An established condition for such trajectories is to have cusp points inside the joint space that must be encircled. This paper presents an approach based on the notion of uniqueness domains to explain this behaviour.

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.

Consider a parametric system of n polynomial equations and r polynomial inequations in n unknowns and s parameters, with rational coefficients. A recurrent problem is to determine some open set in the parameter space where the considered parametric system admits a constant number of real solutions. Following the works of Lazard and Rouillier, this can be done by the computation of a discriminant variety. Let d bound the degree of the input's polynomials, and σ bound the bit-size of their coefficients. Based on some usual assumptions for the applications we prove that the degree of the computed minimal discriminant variety is bounded by D := (n+r)d(n+1). Moreover we provide in this case a deterministic method which computes the minimal discriminant variety in σO(1)DO(n+s) bit-operations on a deterministic Turing machine.