Divide and Conquer Roadmap for Algebraic Sets
Résumé
Let $\R$ be a real closed field, and $\D \subset\R$ an ordered domain. We describe an algorithm that given as input a polynomial $P \in \D[X_1, \ldots, X_k]$, and a finite set, $A$, of points contained in $V = Zer(P,\R^k)$, computes a roadmap of $V$ containing $A$. The complexity of the algorithm, measured by the number or arithmetic operations in $\D$, is bounded by $(k d)^{\tilde{O}(k)}$, where $d = \deg(P)$, where we also assume that the $card(A)$, as well as the degrees of the univariate representations describing the points in $A$, are both bounded by $d^{O(k)}$. The size of the output, as well as the degrees of the polynomials appearing in the output, are also bounded by $(k d)^{\tilde{O}(k)}$. Given that the number of semi-algebraically connected components of such a variety could be as large as $(\Omega(d))^k$, this complexity can be considered to be quasi-optimal. The best previous algorithm for this problem had complexity $d^{O(k^{3/2})}$. As an application of our result we prove that for any real algebraic subset $V$ of $\mathbbm{R}^k$ defined by a polynomial of degree $d$, and any connected component $C$ of $V$ contained in the unit ball, the maximum length and complexity of a semi-algebraic path with image in $C$ that is needed to connect any two points of $C$ is bounded by $(k d)^{\tilde{O}(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.