Topological complexity of the range searching. (English) Zbl 0951.68024
Summary: 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 by H. Fournier and P. Koiran [Proc. ACM STOC, 507-513 (1998)].
References:
| [1] | Basu, S.; Pollack, R.; Roy, M.-F., On the combinatorial and algebraic complexity of quantifier elimination, J. Assoc. Comput. Mach., 6, 1002-1045 (1996) · Zbl 0885.68070 |
| [2] | H. Fournier and P. Koiran, Are lower bounds easier over the reals? in Proc. ACM STOC, 1998, pp. 507-513.; H. Fournier and P. Koiran, Are lower bounds easier over the reals? in Proc. ACM STOC, 1998, pp. 507-513. · Zbl 1028.68051 |
| [3] | Grigoriev, D., The complexity of deciding Tarski algebra, J. Symbolic Comput., 65-108 (1988) · Zbl 0689.03021 |
| [4] | Mayr auf der Heide, F., Fast algorithms for \(n\)-dimensional restrictions of hard problems, J. Assoc. Comput. Mach., 3, 740-747 (1988) |
| [5] | Meiser, S., Point location in arrangements of hyperplanes, Inform. and Comput., 2, 286-303 (1993) · Zbl 0781.68121 |
| [6] | Smale, S., On the topology of algorithms, J. Complexity, 3, 81-89 (1987) · Zbl 0639.68042 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
