On the complexity of solving bivariate systems

par Yacine Bouzidi (INRIA Nancy)

jeudi 28 nov. 2013, 10:30 → 11:30 Europe/Paris

XR.203 (Bâtiment XLIM)

A fundamental problem in computational geometry is the computation of the topology of a real algebraic plane curve given by its implicit equation, that is, the computation of a set of polygonal lines that approximates the curve while preserving its topology. A critical step in many algorithms computing the topology of a plane curve is the computation of the set of singular and extreme points (with respect to one direction) of this curve, which is equivalent to the computation of the solutions of bivariate systems defined by the curve and some of its partial derivatives. In this presentation, we study form theoretical and practical points of view, the problem of solving systems of bivariate polynomials with coefficients in Z. More precisely, we investigate the computation of a Rational Univariate Representation (RUR) of the solutions of a bivariate system, that is, a one-to-one mapping that sends the roots of a univariate polynomial to the solutions of the bivariate system. Such a representation is very useful to compute efficiently with the solutions of a bivariate system. We present both theoretical and practical results concerning the computation and the use of such a representation in the case of bivariate systems and show the impact of these results on our initial problem of computing the topology of curves.