A Baby StepGiant Step Roadmap Algorithm for General Algebraic Sets
Let \(\mathrm {R}\) be a real closed field and \(\mathrm{D}\subset \mathrm {R}\) an ordered domain. We present an algorithm that takes as input a polynomial \(Q \in \mathrm{D}[X_{1},\ldots ,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 = \deg (Q)\ge 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}),\) whose complexity is also bounded by \(d^{O(k \sqrt{k})},\) where \(d = \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})}.\)
roadmaps real algebraic variety baby step-giant step primary 14q20 secondary 14p05 68w05