Topological Complexity of the Range Searching

AbstractWe 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 finds all feasible signs vectors of these polynomials, with the (topological) complexity logarithmic in the number of signs vectors. This answers the problem posed by H. Fournier and P. Koiran (1998, in “Proc. ACM STOC,” pp. 507–513)