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...
Published in: | Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation |
---|---|
Main Authors: | , , |
Other Authors: | , , , , , , , |
Format: | Conference Object |
Language: | English |
Published: |
HAL CCSD
2023
|
Subjects: | |
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 |
id |
ftunivlille:oai:HAL:hal-04000614v2 |
---|---|
record_format |
openpolar |
spelling |
ftunivlille:oai:HAL:hal-04000614v2 2024-06-23T07:57:14+00:00 Algorithm for connectivity queries on real algebraic curves Islam, Nazrul Poteaux, Adrien Prébet, Rémi 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 Tromsø, Norway 2023-07-24 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 en eng HAL CCSD info:eu-repo/semantics/altIdentifier/arxiv/2302.11347 info:eu-repo/semantics/altIdentifier/doi/10.1145/3597066.3597081 hal-04000614 https://hal.science/hal-04000614 https://hal.science/hal-04000614v2/document https://hal.science/hal-04000614v2/file/algcurves-merged.pdf ARXIV: 2302.11347 doi:10.1145/3597066.3597081 http://creativecommons.org/licenses/by/ info:eu-repo/semantics/OpenAccess ISSAC '23: Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation ISSAC 2023 - 48th International Symposium on Symbolic and Algebraic Computation https://hal.science/hal-04000614 ISSAC 2023 - 48th International Symposium on Symbolic and Algebraic Computation, Jul 2023, Tromsø, Norway. ⟨10.1145/3597066.3597081⟩ https://issac-conference.org/ 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] info:eu-repo/semantics/conferenceObject Conference papers 2023 ftunivlille https://doi.org/10.1145/3597066.3597081 2024-06-03T14:48:20Z 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. Conference Object Tromsø LillOA (HAL Lille Open Archive, Université de Lille) Norway Tromsø Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation 345 353 |
institution |
Open Polar |
collection |
LillOA (HAL Lille Open Archive, Université de Lille) |
op_collection_id |
ftunivlille |
language |
English |
topic |
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] |
spellingShingle |
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] Islam, Nazrul Poteaux, Adrien Prébet, Rémi Algorithm for connectivity queries on real algebraic curves |
topic_facet |
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] |
description |
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. |
author2 |
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 |
author |
Islam, Nazrul Poteaux, Adrien Prébet, Rémi |
author_facet |
Islam, Nazrul Poteaux, Adrien Prébet, Rémi |
author_sort |
Islam, Nazrul |
title |
Algorithm for connectivity queries on real algebraic curves |
title_short |
Algorithm for connectivity queries on real algebraic curves |
title_full |
Algorithm for connectivity queries on real algebraic curves |
title_fullStr |
Algorithm for connectivity queries on real algebraic curves |
title_full_unstemmed |
Algorithm for connectivity queries on real algebraic curves |
title_sort |
algorithm for connectivity queries on real algebraic curves |
publisher |
HAL CCSD |
publishDate |
2023 |
url |
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 |
op_coverage |
Tromsø, Norway |
geographic |
Norway Tromsø |
geographic_facet |
Norway Tromsø |
genre |
Tromsø |
genre_facet |
Tromsø |
op_source |
ISSAC '23: Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation ISSAC 2023 - 48th International Symposium on Symbolic and Algebraic Computation https://hal.science/hal-04000614 ISSAC 2023 - 48th International Symposium on Symbolic and Algebraic Computation, Jul 2023, Tromsø, Norway. ⟨10.1145/3597066.3597081⟩ https://issac-conference.org/ |
op_relation |
info:eu-repo/semantics/altIdentifier/arxiv/2302.11347 info:eu-repo/semantics/altIdentifier/doi/10.1145/3597066.3597081 hal-04000614 https://hal.science/hal-04000614 https://hal.science/hal-04000614v2/document https://hal.science/hal-04000614v2/file/algcurves-merged.pdf ARXIV: 2302.11347 doi:10.1145/3597066.3597081 |
op_rights |
http://creativecommons.org/licenses/by/ info:eu-repo/semantics/OpenAccess |
op_doi |
https://doi.org/10.1145/3597066.3597081 |
container_title |
Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation |
container_start_page |
345 |
op_container_end_page |
353 |
_version_ |
1802650777065357312 |