Topological Complexity of the Range Searching

Dima Grigoriev

IMR Université de Rennes-1 Rennes 35042 France

             E-mail: dima@maths.univ-rennes1.fr

Abstract

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 finds 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].

1 Range Searching Problem

Let polynomials f_{1}, …, f_{m} ∈ ℝ[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 ∈ ℝ[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 ∈ ℝ^{n} with different signs vectors (sgn(f_{1}), …, sgn(f_{m}))(x) ≠ (sgn(f_{1}), …, sgn(f_{m}))(y) arrive to different 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)} where deg(f_{i}) ≤ d, 1 ≤ i ≤ n, or in [BPR96] a better bound N ≤ ((2^{n} + \binom{m}{n})d^{n})^{O(1)}. The following result answers the problem posed in section 4.2 [FK98].

Theorem. There exists a TDT solving the range searching problem with a topological complexity at most O(log N).

Obviously, the bound is sharp.

Let us also mention that for linear polynomials deg(f_{i}) = 1, 1 ≤ i ≤ m the range searching problem can be solved even with a small computational complexity log^{O(1)} N by linear decision trees [M88],[M93].

2 Divide-and-conquer of the signs vectors

The desired in the theorem TDT will be designed (notice that the proof is nonconstructive) in two stages. At the first one we design a TDT T_{0} which solves the range searching problem with respect to the equality to zero, i.e. if for two input points x, y truncated signs vectors (sgn_{0}(f_{1}), …, sgn_{0}(f_{m}))(x) ≠ (sgn_{0}(f_{1}), …, sgn_{0}(f_{m}))(y) are different (where sgn_{0} attains just two values distinguishing zero and nonzeroes), then x, y should arrive in different leaves.

For conveniency reasons we represent a truncated signs vector (sgn_{0}(f_{1}), …, sgn_{0}(f_{m}))(x) by a subset I ⊂ {1, …, m} consisting of all 1 ≤ i ≤ m such that f_{i}(x) = 0. Denote by N_{0} ≤ N the number of all feasible truncated signs vectors.

For a subset I ⊂ {1, …, m} denote f[I] = ∑_{i∈I} f_{i}^{2}. Ordering all subsets I corresponding to the feasible truncated signs vectors in any way compatible with non-increasing of their cardinalities, we take in this ordering the first [N_{0}/2] subsets and denote the family of these subsets by S. The polynomial f_{S} = ∏_{I∈S} f[I] is the first testing polynomial attached to the root of TDT T_{0} which we design. Observe that the inputs with truncated signs vectors from S satisfy the test f_{S} = 0 (or equivalently f_{S} ≤ 0) and the inputs with the truncated signs vectors from the rest of N_{0} − [N_{0}/2] ones satisfy the test f_{S} > 0.

Continuing this divide-and-conquer process we each time take the first half of the set of truncated sign vectors w.r.t. the chosen ordering. This completes the design of TDT T_{0}. In fact, one could diminish the degrees of testing polynomials by taking the products only over the minimal (now w.r.t. the set inclusion relation) subsets I (say, from the family S in the first testing polynomial above), but anyway we are interested just in the topological complexity and do not need this remark.

To design the entire TDT T we fix for the time being a certain truncated signs vector I_{0} and consider any leaf a of T_{0} which corresponds to I_{0}. The next purpose is to design a TDT T_{1} which deals just with I_{0} and to glue T_{1} to a. The design of T_{1} relies on the following lemma.

Lemma. Let vectors u_{1}, …, u_{N} ∈ GF (2)^{k} be pairwise distinct (N ≥ 6). Then there exists a vector v ∈ GF (2)^{k} such that

(1/3)N ≤ |{1 ≤ i ≤ N : vu_{i} = 0}| ≤ (2/3)N.

Proof. Suppose the contrary. Consider the subset V of all vectors v ∈ GF (2)^{k} such that |{1 ≤ i ≤ N : vu_{i} = 1}| < (1/3)N. We claim that

(i) V is a subspace;

(ii) dim(V) ≥ k − 1.

To prove (i) take any two vectors v_{1}, v_{2} ∈ V, then N_{1} = |{1 ≤ i ≤ N : (v_{1}+v_{2})u_{i} = 1}| < (2/3)N, therefore, due to the supposition, N_{1} < (1/3)N which proves (i). To prove (ii) take any two vectors w_{1}, w_{2} ∈ GF (2)^{k} − V, then N_{2} = |{1 ≤ i ≤ N : (w_{1} + w_{2})u_{i} = 1}| < (2/3)N, hence again due to the supposition N_{2} < (1/3)N, i.e. w_{1} + w_{2} ∈ V which proves (ii).

For each vector u_{i}, 1 ≤ i ≤ N except, perhaps, u_{i} = 0 and a unique vector presumably orthogonal to V (which does exist if dim(V) = k −1), exactly half among the inner products vu_{i}, v ∈ V are equal to zero. Thus, there exists v ∈ V such that |{1 ≤ i ≤ N : vu_{i} = 0}| ≥ (N − 2)/2 that contradicts the supposition. The lemma is proved.

We apply the lemma to the set of N^{(0)} ≤ N signs vectors in GF (2)^{m−|I_{0}|} obtained from vectors of GF (2)^{m} by deleting coordinates at the positions from I_{0}, and moreover, replacing each sign ”<” by 1 and each sign ”>” by 0. Take a vector v ∈ GF (2)^{m−|I_{0}|} provided by the lemma, and as the first testing polynomial of T_{1} attached to its root we consider ∏_{j∉I_{0}} f_{j}^{v^{(j)}} where v^{(j)} are the coordinates of v indexed by the elements from the set {1, …, m} − I_{0}. Then the input points with the signs vectors u ∈ GF (2)^{m−|I_{0}|} satisfying uv = 0 or uv = 1, respectively, are separated just by the first test.

Continuing this divide-and-conquer process (in a similar way to the first stage) we apply the lemma at each step to the current set of signs vectors. The depth of the designed TDT T_{1} is thereby O(log N^{(0)}). Together with the design of T_{0} at the first stage this completes the proof of the theorem.

3 Comments and an open question

Similar to [M88] one can prove that any problem which can be solved with a polynomial parallel complexity over the reals (in other words, belonging to the class P AR_{ℝ} [FK98]) has also a polynomial topological complexity.

It would be also interesting to design a TDT with a small (similar to the theorem) topological complexity solving the range searching problem for a set of polynomials f_{1}, …, f_{m} ∈ F [X_{1}, …, X_{n}] where F is an algebraically closed field and the sign vectors are understood as the truncated ones (see above).

Acknowledgement

This work was done during the stay at MSRI. The author is also grateful to Pascal Koiran for the useful discussions.

References

[BPR96] S. Basu, R. Pollack, M.-F. Roy On the Combinatorial and Algebraic Complexity of Quantifier Elimination., J. ACM, 1996, 6, pp. 1002–1045.

[FK98] H. Fournier, P. Koiran, Are Lower Bounds Easier over the Reals?, Proc. ACM STOC, 1998, pp. 507–513.

[G88] D. Grigoriev, The Complexity of Deciding Tarski Algebra., J.Symb.Comput., 1988, pp. 65–108.

[M88] F. Mayr auf der Heide, Fast algorithms for n-dimensional Restrictions of Hard Problems., J. ACM, 1988, 3, pp. 740–747.

[M93] S. Meiser, Point Location in Arrangements of Hyperplanes, Information and Computation, 1993, 2, pp. 286–303.

[S87] S. Smale, On the Topology of Algorithms, J. Complexity, 1987, 3, pp. 81–89.