A baby step-giant step roadmap algorithm for general algebraic sets

Abstract

Let $\mathrm{R}$ be a real closed field and $\mathrm{D}\subset \mathrm{R}$ an ordered domain. We give an algorithm that takes as input a polynomial $Q\in \mathrm{D}[X_1,\dots ,X_k]$, and computes a description of a roadmap of the set of zeros, $\mathrm{Zer}(Q,{\mathrm{R}}^k)$, of $Q$ in ${\mathrm{R}}^k$. The complexity of the algorithm, measured by the number of arithmetic operations in the ordered domain $\mathrm{D}$, is bounded by $d^{O(k\sqrt{k})}$, where $d=\mathrm{deg}(Q)\ge 2$. As a consequence, there exist algorithms for computing the number of semi-algebraically connected components of a real algebraic set, $\mathrm{Zer}(Q,{\mathrm{R}}^k)$, whose complexity is also bounded by $d^{O(k\sqrt{k})}$, where $d=\mathrm{deg}(Q)\ge 2$. The best previously known algorithm for constructing a roadmap of a real algebraic subset of ${\mathrm{R}}^k$ defined by a polynomial of degree $d$ has complexity $d^{O(k^2)}$.

48 pages, 2 figures. Final version to appear in Foundations of Computational Mathematics

Cited by in corpus (3)

• Program Verification in the presence of complex numbers, functions with branch cuts etc
• NUROA: A Numerical Roadmap Algorithm
• Minimizing Movement: Fixed-Parameter Tractability