On range searching with semialgebraic sets. (English) Zbl 1493.68366
Havel, Ivan M. (ed.) et al., Mathematical foundations of computer science 1992. 17th international symposium, Prague, Czechoslovakia, August 24–28, 1992. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 629, 1-13 (1992).
Summary: Let \(P\) be a set of \(n\) points in \(\mathbb{R}^d\) (\(d\) a small fixed positive integer), and let \(\Gamma\) be a collection of subsets of \(\mathbb{R}^d\), each of which is defined by a constant number of bounded degree polynomials. The \(\Gamma\)-range searching problem is defined as: Preprocess \(P\) into a data structure, so that all points of \(P\) lying in a given \(\gamma \in \Gamma\) can be counted (or reported) efficiently. Generalizing the simplex range searching techniques, we construct a data structure for \(\Gamma\)-range searching with nearly linear space and preprocessing time, which can answer a query in time \(O(n^{1-1/ b+ \delta})\), where \(d \leq b \leq 2 d -3\) and \(\delta >0\) is an arbitrarily small constant. The actual value of \(b\) is related to the problem of partitioning arrangements of algebraic surfaces into constant-complexity cells.
For the entire collection see [Zbl 1415.68030].
For the entire collection see [Zbl 1415.68030].
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 14P10 | Semialgebraic sets and related spaces |
| 68P05 | Data structures |
References:
| [1] | A. Aggarwal, M. Hansen, and T.Leighton. Solving query-retrieval problems by compacting Voronoi diagrams. Proc. 21st ACM Symposium on Theory of Computing, 1990, 331-340. |
| [2] | N. Alon, D. Haussler, E. Welzl, and G. Wöginger. Partitioning and geometric embedding of range spaces of finite Vapnik-Chervonenkis dimension. In Proc. 3. ACM Symposium on Computational Geometry, pages 331-340, 1987. |
| [3] | B. Aronov, M. Pellegrini, and M. Sharir, On the zone of a surface in a hyperplane arrangement. Discrete & Computational Geometry, to appear. · Zbl 0773.52007 |
| [4] | P. K. Agarwal and M. Sharir. Applications of a new space partitioning scheme. In Proc. 2. Workshop on Algorithms and Data Structures, 1991. · Zbl 0766.68131 |
| [5] | B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir. Point-location in real-algebraic varieties and its applications. In Proc. 16th International Colloquium on Automata, Languages and Programming, pages 179-192, 1989. · Zbl 0702.68064 |
| [6] | B. Chazelle and J. Friedman. A deterministic view of random sampling and its use in geometry. Combinatorica, 10(3):229-249, 1990. · Zbl 0715.68036 · doi:10.1007/BF02122778 |
| [7] | B. Chazelle. Lower bounds on the complexity of polytope range searching. J. Amer. Math. Soc, 2(4):637-666, 1989. · Zbl 0695.68032 · doi:10.2307/1990891 |
| [8] | B. Chazelle. Cutting hyperplanes for divide-and-conquer. Tech. report CS-TR-335-91, Princeton University, 1991. Preliminary version: Proc. 32. IEEE Symposium on Foundations of Computer Science, October 1991. · Zbl 0784.52018 |
| [9] | K. L. Clarkson and P. Shor. New applications of random sampling in computational geometry II. Discrete & Computational Geometry, 4:387-421, 1989. · Zbl 0681.68060 · doi:10.1007/BF02187740 |
| [10] | B. Chazelle, M. Sharir, and E. Welzl. Quasi-optimal upper bounds for simplex range searching and new zone theorems. In Proc. 6. ACM Symposium on Computational Geometry, pages 23-33, 1990. · Zbl 0788.68141 |
| [11] | B. Chazelle and E. Welzl. Quasi-optimal range searching in spaces of finite VC-dimension. Discrete & Computational Geometry, 4:467-490, 1989. · Zbl 0681.68081 · doi:10.1007/BF02187743 |
| [12] | D. Dobkin and H. Edelsbrunner. Space searching for intersecting objects. Journal of Algorithms, 8:348-361, 1987. · Zbl 0646.68077 · doi:10.1016/0196-6774(87)90015-0 |
| [13] | H. Edelsbrunner. Algorithms in Combinatorial Geometry. Springer-Verlag, Berlin-Heidelberg-New York, 1987. · Zbl 0634.52001 |
| [14] | D. Haussler and E. Welzl. ε-nets and simplex range queries. Discrete & Computational Geometry, 2:127-151, 1987. · Zbl 0619.68056 · doi:10.1007/BF02187876 |
| [15] | J. Komlós, J. Pach, and G. Wöginger. Almost tight bounds for epsilon-nets. Discrete & Computational Geometry, 1992. To appear. |
| [16] | J. Matoušek. Approximations and optimal geometric divide-and-conquer. In Proc. 23. ACM Symposium on Theory of Computing, pages 506-511, 1991. |
| [17] | J. Matoušek. Cutting hyperplane arrangements. Discrete & Computational Geometry, 6(5):385-406, 1991. · Zbl 0765.68210 |
| [18] | J. Matoušek. Efficient partition trees. In Proc. 7. ACM Symposium on Computational Geometry, pages 1-9, 1991. Also to appear in Discrete & Computational Geometry. |
| [19] | J. Matoušek. Reporting points in halfspaces. Proc. 32nd IEEE Symposium on Foundations of Computer Science, 1991, pp. 207-215. |
| [20] | J. Matoušek. Range searching with efficient hierarchical cuttings. In Proc. 8. ACM Symposium on Computational Geometry, 1992. To appear. · Zbl 0774.68101 |
| [21] | F. Preparata and M. I. Shamos. Computational Geometry — An Introduction. Springer-Verlag, 1985. · Zbl 0759.68037 |
| [22] | D. E. Willard. Polygon retrieval. SIAM Journal on Computing, 11:149-165, 1982. · Zbl 0478.68060 · doi:10.1137/0211012 |
| [23] | F. F. Yao and A. C. Yao. A general approach to geometric queries. In Proc. 17. ACM Symposium on Theory of Computing, pages 163-168, 1985. |
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.
