Computing the connected components of real algebraic curves
This work addresses a computational geometry problem relevant to fields like robotics and optical design, but it appears incremental as it improves on existing complexity bounds.
The paper tackles the problem of computing semi-algebraic descriptions for connected components of real algebraic curves, with applications in optical system design and robotics, and presents a new algorithm that achieves lower complexity than the best known method for computing isotopic graphs.
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.