Computing the connected components of real algebraic curves

2026/03/17 by Elisabetta Rocchi, Mohab Safey El Din · 1 voice
Computer Science · Mathematics · #cs.SC #math.AG

paper · pdf · doi:10.1145/3815436.3815466

Abstract

Connected components of real algebraic sets are semi-algebraic, i.e. they are described by a boolean formula whose atoms are polynomial constraints with real coefficients. Computing such descriptions finds topical applications in optical system design and robotics. In this paper, we design a new algorithm for computing such semi-algebraic descriptions for real algebraic curves. Notably, its complexity is less than the best known one for computing a graph which is isotopic to the real space curve under study.

Citations

• Refined bit complexity for the computation of at least one point per connected component of a smooth complete intersection real algebraic set
• A certified classification of first-order controlled coaxial telescopes
• Bit complexity for computing one point in each connected component of a smooth real algebraic set
• Effective Coefficient Asymptotics of Multivariate Rational Functions via Semi-Numerical Algorithms for Polynomial Systems
• Bounds for polynomials on algebraic numbers and application to curve topology
• CAD Adjacency Computation Using Validated Numerics
• Bit complexity for multi-homogeneous polynomial system solving Application to polynomial minimization
• A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets
• From Approximate Factorization to Root Isolation with Application to Cylindrical Algebraic Decomposition
• Certified Rational Parametric Approximation of Real Algebraic Space Curves with Local Generic Position Method
• Exact Symbolic-Numeric Computation of Planar Algebraic Curves
• Bit-size estimates for triangular sets in positive dimension
• Complete Subdivision Algorithms, II: Isotopic Meshing of Singular Algebraic Curves
• On the Computation of the Topology of a Non-Reduced Implicit Space Curve
• Commutative Algebra
• Algorithms in Real Algebraic Geometry

Discussions

• Elisabetta Rocchi (PolSys), Mohab Safey El Din (PolSys): Computing the connected components of real algebraic curves https://arxiv.org/abs/2603.16283 https://arxiv.org/pdf/2603.16283 https://arxiv.org [bsky, 0 points, 0 comments]

Related

• Segmentation of real algebraic plane curves
• A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets
• Computing points in connected components defined by a real inequation: algorithms, complexity and implementations, Part I
• Certified algebraic curve projections by path tracking
• Numerically computing real points on algebraic sets