Divide and Conquer Roadmap for Algebraic Sets

Abstract

Let $\mathrm{R}$ be a real closed field, and $\mathrm{D}\subset \mathrm{R}$ an ordered domain. We describe an algorithm that given as input a polynomial $P\in \mathrm{D}[X_1,\dots ,X_k]$, and a finite set, $\mathcal{A}=\{p_1,\dots ,p_m\}$, of points contained in $V=\mathrm{Zer}(P,{\mathrm{R}}^k)$ described by real univariate representations, computes a roadmap of $V$ containing $\mathcal{A}$. The complexity of the algorithm, measured by the number of arithmetic operations in $\mathrm{D}$ is bounded by $\left({\sum }_{i=1}^m{D}_i^{O({\log }^2(k))}+1\right)(k^{\log (k)}d{)}^{O(k{\log }^2(k))}$, where $d=\mathrm{deg}(P)$, and $D_i$ is the degree of the real univariate representation describing the point $p_i$. The best previous algorithm for this problem had complexity $\mathrm{card}(\mathcal{A}{)}^{O(1)}{d}^{O(k^{3/2})}$ due to Basu, Roy, Safey-El-Din, and Schost (2012), where it is assumed that the degrees of the polynomials appearing in the representations of the points in $\mathcal{A}$ are bounded by $d^{O(k)}$. As an application of our result we prove that for any real algebraic subset $V$ of ${\mathbb{R}}^k$ defined by a polynomial of degree $d$, any connected component $C$ of $V$ contained in the unit ball, and any two points of $C$, there exist a semi-algebraic path connecting them in $C$, of length at most $(k^{\log (k)}d{)}^{O(k\log (k))}$, consisting of at most $(k^{\log (k)}d{)}^{O(k\log (k))}$ curve segments of degrees bounded by $(k^{\log (k)}d{)}^{O(k\log (k))}$. While it was known previously, by a result of D'Acunto and Kurdyka, that there always exists a path of length $(O(d){)}^{k-1}$ connecting two such points, there was no upper bound on the complexity of such a path.

Notation 5.4 is modified and the proof of Proposition 5.5 are corrected. These changes do not affect the main results of the paper

Cited by in corpus (9)

• Algorithms in Real Algebraic Geometry: A Survey
• Solving parametric systems of polynomial equations over the reals through Hermite matrices
• Vandermonde varieties, mirrored spaces, and the cohomology of symmetric semi-algebraic sets
• Deciding Cuspidality of Manipulators through Computer Algebra and Algorithms in Real Algebraic Geometry
• Robots, computer algebra and eight connected components
• A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets
• Algorithm for connectivity queries on real algebraic curves
• Computing the Real Isolated Points of an Algebraic Hypersurface
• Quantitative approximate definable choices