Algorithm for Connectivity Queries on Real Algebraic Curves
From MaRDI portal
Abstract: 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 , where 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.
Cites work
- scientific article; zbMATH DE number 3572315 (Why is no real title available?)
- scientific article; zbMATH DE number 1201576 (Why is no real title available?)
- scientific article; zbMATH DE number 704831 (Why is no real title available?)
- scientific article; zbMATH DE number 2149738 (Why is no real title available?)
- A Nearly Optimal Algorithm for Deciding Connectivity Queries in Smooth and Bounded Real Algebraic Sets
- A baby step-giant step roadmap algorithm for general algebraic sets
- A concise proof of the Kronecker polynomial system solver from scratch
- A worst-case bound for topology computation of algebraic curves
- Algebraic Geometry. I: Complex projective varieties.
- Algorithms in real algebraic geometry
- An improved upper complexity bound for the topology computation of a real algebraic plane curve
- Basic Algebraic Geometry 2
- Bounds for polynomials on algebraic numbers and application to curve topology
- Certified rational parametric approximation of real algebraic space curves with local generic position method
- Complete subdivision algorithms, II
- Computation of the dual of a plane projective curve
- Computation of the topology of real algebraic space curves
- Computing Roadmaps of General Semi-Algebraic Sets
- Computing roadmaps of semi-algebraic sets on a variety
- Connectivity queries on curves in Rn
- Constructing roadmaps of semi-algebraic sets. I: Completeness
- Divide and conquer roadmap for algebraic sets
- Exact symbolic-numeric computation of planar algebraic curves
- Fast and exact geometric analysis of real algebraic plane curves
- From approximate factorization to root isolation with application to cylindrical algebraic decomposition
- Generators of the ideal of an algebraic space curve
- Ideals, Varieties, and Algorithms
- Introduction to algorithms.
- Knots.
- Modern computer algebra
- On the asymptotic and practical complexity of solving bivariate systems over the reals
- On the bit complexity of polynomial system solving
- On the complexity of computing the topology of real algebraic space curves
- On the complexity of computing with planar algebraic curves
- On the complexity of real solving bivariate systems
- On the computation of the topology of a non-reduced implicit space curve
- On the computation of the topology of plane curves
- On the exact computation of the topology of real algebraic curves
- On the isotopic meshing of an algebraic implicit surface
- On the topology of real algebraic plane curves
- Pinch-points and multiple locus of generic projections of singular varieties
- Positive dimensional parametric polynomial systems, connectivity queries and applications in robotics
- Robots, computer algebra and eight connected components
- Subdivision methods for the topology of 2d and 3d implicit curves
- Topology and arrangement computation of semi-algebraic planar curves
- Topology of real algebraic space curves
- Trisecant Lemma for nonequidimensional varieties
Cited in
(3)
This page was built for publication: Algorithm for Connectivity Queries on Real Algebraic Curves
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6060394)
