On Computing a Set of Points Meeting Every Cell Defined by a Family of Polynomials on a Variety

AbstractWe consider a family ofspolynomials, P = {P1, …,Ps}, inkvariables with coefficients in a real closed fieldR, each of degree at mostd, and an algebraic varietyVof real dimensionk′ which is defined as the zero set of a polynomialQof degree at mostd. The number of semi-algebraically connected components of all non-empty sign conditions on P overVis bounded bysk′(O(d))k. In this paper we present a new algorithm to compute a set of points meeting every semi-algebraically connected component of each non-empty sign condition of P overV. Its complexity issk′ + 1dO(k). This interpolates a sequence of results between the Ben-Or–Kozen–Reif algorithm which is the casek′ = 0, in one variable, and the Basu–Pollack–Roy algorithm which is the casek′ =k. It improves the results where the same problem was solved in timesk′ + 1dO(k′k)