We prove an existence of a topological decision tree which solves the range searching problem for a system of real polynomials, in other words, the tree nds all feasible signs vectors of these polynomials, with the (topological) complexity logarithmic in the number of signs vectors. This answers the problem posed in FK98]. Let polynomials f 1 ; : : : ; f m 2 R X 1 ; : : : ; X n ]. Our purpose is to solve the range searching problem FK98] by means of topological decision trees (TDT) S87]. Namely, TDT allows tests of the form "P(x) > 0?" for arbitrary polynomials P 2 R X 1 ; : : : ; X n ] (thus, we ignore the cost of the computations). We say that a TDT solves the range searching problem for the polynomials f 1 ; : : :; f m if any two input points x; y 2 R n with di erent signs vectors (sgn(f 1 ); : : :; sgn(f m ))(x) 6 = (sgn(f 1 ); : : : ; sgn(f m ))(y) arrive to di erent leaves of the TDT. As usual, sgn could attain three values. By the topological complexity of a TDT we mean its depth. Denote by N the number of all feasible signs vectors (sgn(f 1 ); : : :; sgn(f m ))(x). It is well known (see e.g. G88]) that N (md) O(n)
On the other hand, Grigoriev REF exhibits a family of polynomials for the same task which minimizes the number of comparisons at the expense of the number of arithmetic operations.
Topological Complexity of the Range Searching
J. Complexity
Computer Science Mathematics