Quasi-optimal range searching in spaces of finite VC-dimension. (English) Zbl 0681.68081

The paper deals with the range searching problem, i.e. given a finite set S of points in d-dimensional space \(E^ d\) and a query region \(q\subseteq E^ d\), report or count the points of \(S\cap q\). On more abstract level one can consider a range space (X,R), where X is an arbitrary set (the elements of X are called points) and R is a subset of its power set (the members of R are called ranges). The authors consider the use of partition trees to solve this problem and show that “good” partition trees (i.e. with sublinear query time and linear size) can be characterized as those defined by range spaces of finite Vapnik- Chervonenkis dimension. Then they show that simplex and spherical range searching problems are both solvable in \(\theta (n^{1-1/d}\alpha (n))\) query time and \(\theta\) (n) storage in the arithmetical model, where \(\alpha\) (n) denotes the inverse Ackerman function. Finally algorithms for polygon, disk and tetrahedron range searching on RAM or pointer machine are discussed.
Reviewer: J.Vyskoc


68P10 Searching and sorting
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI EuDML


[1] Alon, N., Haussler, D., Welzl, E., Wöginger, G. Partitioning and geometric embedding of range spaces of finite Vapnik-Chervonenkis dimension,Proc. 3rd Ann. ACM Symp. Comput. Geom. (1987), 331-340.
[2] Assouad, P. Densité et dimension,Ann. Inst. Fourier (Grenoble)33 (1983), 233-282. · Zbl 0504.60006 · doi:10.5802/aif.938
[3] Chazelle, B. Polytope range searching and integral geometry,Proc. 28th Ann. IEEE Symp. Found. Comput. Sci. (1987), 1-10. To appear inJ. Amer. Math. Soc.
[4] Chazelle, B., Guibas, L. J. Visibility and intersection problems in plane geometry,Proc. 1st Ann. ACM Symp. Comput. Geom. (1985), 135-146. To appear inDiscrete Comput. Geom. · Zbl 0695.68033
[5] Dobkin, D. P., Kirkpatrick, D. G. Fast detection of polyhedral intersection,Theoret. Comput. Sci.27 (1983), 241-253. · Zbl 0553.68033 · doi:10.1016/0304-3975(82)90120-7
[6] Dudley, R. M. Central limit theorems for empirical measures,Ann. Probab.6 (1978), 899-929. · Zbl 0404.60016 · doi:10.1214/aop/1176995384
[7] Edelsbrunner, H.Algorithms in Combinatorial Geometry, Springer-Verlag, Heidelberg, 1987. · Zbl 0634.52001 · doi:10.1007/978-3-642-61568-9
[8] Edelsbrunner, H., Guibas, L. J., Hershberger, J., Seidel, R., Sharir, M., Snoeyink, J., Welzl, E. Implicitly representing arrangements of lines or segments.Proc. 4th Ann. ACM Symp. Comput. Geom. (1988), 56-69. · Zbl 0688.68031
[9] Edelsbrunner, H., Welzl, E. Halfplanar range search in linear space andO(n0.695) query time,Inform. Process. Lett.23 (1986), 289-293. · Zbl 0634.68064 · doi:10.1016/0020-0190(86)90088-8
[10] Fredman, M. L. Lower bounds on the complexity of some optimal data structures,SIAM J. Comput.10 (1981), 1-10. · Zbl 0454.68006 · doi:10.1137/0210001
[11] Haussler, D., Welzl, E. Epsilon-nets and simplex range queries,Discrete Comput. Geom.2 (1987), 127-151. · Zbl 0619.68056 · doi:10.1007/BF02187876
[12] Matoušek, J. Spanning trees with low stabbing numbers, manuscript, 1988.
[13] Mehlhorn, K.Data Structures and Algorithms 3: Multidimensional Searching and Computational Geometry, Springer-Verlag, Heidelberg, 1984. · Zbl 0556.68003 · doi:10.1007/978-3-642-69900-9
[14] Monier, L. Combinatorial solutions of multidimensional divide-and-conquer recurrences,J. Algorithms1 (1980), 60-74. · Zbl 0435.68032 · doi:10.1016/0196-6774(80)90005-X
[15] Preparata, F. P., Shamos, M. I.Computational Geometry, Springer-Verlag, New York, 1985. · Zbl 0759.68037 · doi:10.1007/978-1-4612-1098-6
[16] Sauer, N. On the density of families of sets,J. Combin. Theory Ser. A13 (1972), 145-147. · Zbl 0248.05005 · doi:10.1016/0097-3165(72)90019-2
[17] Tarjan, R. E. Efficiency of a good but not linear set union algorithm,J. Assoc. Comput. Geom.22 (1975), 215-225. · Zbl 0307.68029 · doi:10.1145/321879.321884
[18] Vapnik, V. N., Chervonenkis, A. Ya. On the uniform convergence of relative frequencies of events to their probabilities,Theory Probab. Appl.16 (1971), 264-280. · Zbl 0247.60005 · doi:10.1137/1116025
[19] Welzl, E., Wöginger, G. On shatter functions of range spaces, manuscript, 1987.
[20] Willard, D. E. Polygon retrieval,SIAM J. Comput.11 (1982), 149-165. · Zbl 0478.68060 · doi:10.1137/0211012
[21] Yao, A. C. Space-time tradeoff for answering range queries,Proc. 14th Ann. ACM Symp. Theory Comput. (1982), 128-136.
[22] Yao, A. C. On the complexity of maintaining partial sums,SIAM J. Comput.14 (1985), 277-288. · Zbl 0564.68072 · doi:10.1137/0214022
[23] Yao, A. C., Yao, F. F. A general approach tod-dimensional geometric queries,Proc. 17th Ann. ACM Symp. Theory Comput. (1985), 163-168.
[24] Yao, F. F. A 3-space partition and its applications.Proc. 15th Ann. ACM Symp. Theory Comput. (1983), 258-263.
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.