Algorithm for connectivity queries on real ...
Type de document :
Pré-publication ou Document de travail
URL permanente :
Titre :
Algorithm for connectivity queries on real algebraic curves
Auteur(s) :
Islam, Nazrul [Auteur]
Poteaux, Adrien [Auteur]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Prébet, Rémi [Auteur]
Polynomial Systems [PolSys]
Poteaux, Adrien [Auteur]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Prébet, Rémi [Auteur]
Polynomial Systems [PolSys]
Date de publication :
2023-02-22
Mot(s)-clé(s) en anglais :
computational real algebraic geometry
algebraic geometry
symbolic computation
algorithm
algebraic geometry
symbolic computation
algorithm
Discipline(s) HAL :
Informatique [cs]/Calcul formel [cs.SC]
Mathématiques [math]/Géométrie algébrique [math.AG]
Mathématiques [math]/Géométrie algébrique [math.AG]
Résumé en anglais : [en]
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 ...
Lire la suite >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.Lire moins >
Lire la suite >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.Lire moins >
Langue :
Anglais
Collections :
Source :
Date de dépôt :
2023-05-04T23:40:28Z
Fichiers
- document
- Accès libre
- Accéder au document
- algcurves.pdf
- Accès libre
- Accéder au document
- 2302.11347
- Accès libre
- Accéder au document