Let $$\mathrm {R}$$ R be a real closed field and $$\mathrm{D}\subset \mathrm {R}$$ D ? R an ordered domain. We present an algorithm that takes as input a polynomial $$Q \in \mathrm{D}[X_{1},\ldots ,X_{k}]$$ Q ? D [ X 1 , ? , X k ] and computes a description of a roadmap of the set of zeros, $$\mathrm{Zer}(Q,\,\mathrm {R}^{k}),$$ Zer ( Q , R k ) , of Q in $$\mathrm {R}^{k}.$$ R k . The complexity of the algorithm, measured by the number of arithmetic operations in the ordered domain $$\mathrm{D},$$ D , is bounded by $$d^{O(k \sqrt{k})},$$ d O ( k k ) , where $$d = \deg (Q)\ge 2.$$ d = deg ( Q ) ? 2 . As a consequence, there exist algorithms for computing the number of semialgebraically connected components of a real algebraic set, $$\mathrm{Zer}(Q,\,\mathrm {R}^{k}),$$ Zer ( Q , R k ) , whose complexity is also bounded by $$d^{O(k \sqrt{k})},$$ d O ( k k ) , where $$d = \deg (Q)\ge 2.$$ d = deg ( Q ) ? 2 . The best previously known algorithm for constructing a roadmap of a real algebraic subset of $$\mathrm {R}^{k}$$ R k defined by a polynomial of degree d has complexity $$d^{O(k^{2})}.$$ d O ( k 2 ) .
['Saugata Basu', 'M.-F. Roy', 'M. Safey El Din', 'Éric Schost']
A Baby Step---Giant Step Roadmap Algorithm for General Algebraic Sets