\(\epsilon\)-nets and simplex range queries. (English) Zbl 0619.68056

The main problem may be described as follows: given a set of n points in d-dimensional Euclidean space, find a data structure that uses linear storage such that the number of points in any query half space can be determined in sublinear time \(O(n^{\alpha})\). A data structure with \(\alpha =d(d-1)/(d(d-1)+1)+\gamma\) for any \(\gamma >0\) is exhibited. These bounds for \(\alpha\) are better than those previously published for all \(d\geq 2\) by A. Yao and F. Yao [A general approach to d- dimensional geometric queries. Proc. 17th Symp. Theory of Computing, 163- 169 (1985)].
Let X be a set and R be a set of subsets of X, which have a finite dimension in Vapnik-Chervonenkis sense [V. N. Vapnik and A. Ya. Chervonenkis: The theory of pattern recognition (Russian) (1974; Zbl 0284.68070)], A be a finite subset of X and \(0\leq \epsilon \leq 1\). A subset N of A is an \(\epsilon\)-net of A (for R) if N contains a point in each \(r\in R\) such that \(| A\cap r| /| A| >\epsilon\). The authors prove that for \(0<\epsilon\), \(\delta <1\), if N is a subset of A obtained by \(m\geq \max (4/\epsilon \log 2/\delta,8d/\epsilon \log 8d/\epsilon)\) random independent draws, then N is an \(\epsilon\)-net of A with probability at least 1-\(\delta\). Using this result, a partition tree structure that achieves the above query time is constructed.
Reviewer: I.Molchanov


68P10 Searching and sorting
52A22 Random convex sets and integral geometry (aspects of convex geometry)
60C05 Combinatorial probability
05B99 Designs and configurations


Zbl 0284.68070
Full Text: DOI EuDML


[1] P. Assouad, Densite et dimension,Ann. Inst. Fourier (Grenoble)33 (1983), 233-282. · Zbl 0504.60006 · doi:10.5802/aif.938
[2] A. Blumer, A. Ehrenfeucht, D. Haussler, and M. Warmuth, Classifying learnable geometric concepts with the Vapnik-Chervonenkis dimension,Proceedings of the 18th Symposium on Theory of Computation, 273-282, 1986.
[3] B. Chazelle, L. Guibas, and D. T. Lee, The power of geometric duality,Proceedings of the 24th Symposium on Foundations of Computer Science, 217-225, 1983.
[4] K. Clarkson, “A probabilistic algorithm for the post office problem,”Proceedings of the 17th Symposium on Theory of Computation, 175-185, 1985.
[5] K. Clarkson, Further applications of random sampling to computational geometry,Proceedings of the 18th Symposium on Theory of Computation, 414-423, 1986.
[6] R. Cole, Partitioning point sets in 4 dimensions,Proceedings of the Colloquium on Automata, Language and Programming, 111-119, Lecture Notes in Computer Science 194, Springer-Verlag, Berlin, 1985. · Zbl 0571.68090
[7] D. Dobkin and H. Edelsbrunner, Organizing Points in Two and Three Dimensions, Technical Report F130, Technische Universitat Graz, 1984.
[8] D. Dobkin, H. Edelsbrunner, and F. Yao, A 3-space partition and its applications, manuscript.
[9] R. M. Dudley, Central limit theorems for empirical measures,Ann. Probab.6 (1978), 899-929. · Zbl 0404.60016 · doi:10.1214/aop/1176995384
[10] H. Edelsbrunner, Problem P110,Bull. EATCS26 (1985), 239.
[11] H. Edelsbrunner,Algorithms in Combinatorial Geometry, EATCS Monographs in Theoretical Computer Science, Springer-Verlag, Berlin, 1987. · Zbl 0634.52001 · doi:10.1007/978-3-642-61568-9
[12] H. Edelsbrunner and F. Huber, Dissecting Sets of Points in Two and Three-Dimensions, Technical Report F138, Technische Universitat Graz, 1984.
[13] H. Edelsbrunner and E. Welzl, Constructing belts in two-dimensional arrangements with applications,SIAM J. Comput.15 (1986), 271-284. · Zbl 0613.68043 · doi:10.1137/0215019
[14] H. Edelsbrunner and E. Welzl, Halfplanar range search in linear space andO(n0.695) query time,Inform. Process. Lett., to appear. · Zbl 0634.68064
[15] Branko Gruenbaum,Convex Polytopes, Interscience, New York, 1967. · Zbl 0163.16603
[16] N. Sauer, 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] V. N. Vapnik and A. Ya. Chervonenkis, 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
[18] V. N. Vapnik and A. Ya. Chervonenkis,The Theory of Pattern Recognition, Nauka, Moscow, 1974. · Zbl 0284.68070
[19] R. S. Wenocur and R. M. Dudley, Some special Vapnik-Chervonenkis classes,Discrete Math.33 (1981), 313-318. · Zbl 0459.60008 · doi:10.1016/0012-365X(81)90274-0
[20] D. Willard, Polygon retrieval,SIAM J. Comput.11 (1982), 149-165. · Zbl 0478.68060 · doi:10.1137/0211012
[21] I. M. Yaglom and V. G. Bolyansky,Convex Figures, Holt, Rinehart and Winston, New York, 1961 (transl.). · Zbl 0098.35501
[22] F. Yao, A 3-space partition and it applications,Proceedings of the 15th Symposium on Theory of Computation, 258-263, 1983.
[23] A. Yao and F. Yao, A general approach tod-dimensional geometric queries,Proceedings of the 17th Symposium on Theory of Computation, 163-169, 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.