Algorithm for connectivity queries on real algebraic curves

International audience We consider the problem of answering connectivity queries on a real algebraic curve. The curve is given as the real trace of an algebraic curve, assumed to be in generic position, and being defined by some rational parametrizations. The query points are given by a zero-dimensi...

Full description

Bibliographic Details
Published in:Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation
Main Authors: Islam, Nazrul, Poteaux, Adrien, Prébet, Rémi
Other Authors: Diebold Nixdorf, Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Polynomial Systems (PolSys), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), ANR-19-CE48-0015,ECARP,Algorithmes efficaces et exacts pour la planification de trajectoire en robotique(2019), European Project: ECARP
Format: Conference Object
Language:English
Published: HAL CCSD 2023
Subjects:
computational real algebraic geometry
algebraic geometry
symbolic computation
algorithm
[INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC]
[MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG]
Norway
Tromsø
Online Access:https://hal.science/hal-04000614
https://hal.science/hal-04000614v2/document
https://hal.science/hal-04000614v2/file/algcurves-merged.pdf
https://doi.org/10.1145/3597066.3597081
Description
Summary:International audience We consider the problem of answering connectivity queries on a real algebraic curve. The curve is given as the real trace of an algebraic curve, assumed to be in generic position, and being defined by some rational parametrizations. The query points are given by a zero-dimensional parametrization We design an algorithm which counts the number of connected components of the real curve under study, and decides which query point lie in which connected component, in time log-linear in $N^6$ , where $N$ is the maximum of the degrees and coefficient bit-sizes of the polynomials given as input. This matches the currently best-known bound for computing the topology of real plane curves. The main novelty of this algorithm is the avoidance of the computation of the complete topology of the curve.

Similar Items