Solving bivariate algebraic systems and topology of plane curves
type: Dataset
description: A fundamental problem in computational geometry is the computation of the topology of an algebraic plane curve given by its implicit equation, that is, the computation of a graph 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 (wrt x) 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 thesis, we study form theoretical and practical perspectives the problem of solving systems of bivariate polynomials with integer coefficients. 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. We first present a theoretical algorithm for computing the RUR of a bivariate system that improves the best complexity bound for this problem by a factor d^2 where d denote the degree of the input polynomials and allows to derive a new bound on the size of the polynomials of the RUR. We then present an algorithm for computing a RUR that is efficient in practice. This algorithm, based on some random choices and the use of multi-modular computation is probabilistic. We first present a Monte-Carlo variante of this algorithm, and then show how to transforme the latter into a Las-Vegas algorithm by checking the result for correctness. The complexity analysis as well as the experiment we performed show the efficiency of this algorithm.
identifier: NNT: 2014LORR0016
issued: 2026-05-05T14:26:47.989723
language: en
modified: 2026-05-05T14:26:47.989729
contact point: Organization
  fn: CCSD
keyword: infoeu-reposemanticsdoctoralthesis
keyword: infoinfo-cgcomputer-science-cscomputational-geometry-cscg
keyword: infoinfo-sccomputer-science-cssymbolic-computation-cssc
keyword: rational-univariate-representation
keyword: representation-univariee-rationnelle
keyword: resolution-de-systemes-bivaries
keyword: solving-bivariate-systems
keyword: theses
keyword: topologie-de-courbe
keyword: topology-of-curves
landing page: https://theses.hal.science/tel-00979707

Solving bivariate algebraic systems and topology of plane curves
type: Distribution
format: HTML
issued: 2026-05-05T14:26:47.997798
modified: 2026-05-05T14:26:47.972511
access URL: https://theses.hal.science/tel-00979707

test_moissonnage_selune
type: Agent