D Haussler
ABSTRACT
We present a new technique for half-space and simplex range query using Ο(n) space and Ο(na) query time, where a < d(d-1)/d(d-1) + 1 + γ for all dimensions d ≥ 2 and γ > 0. These bounds are better than those previously published for all d ≥ 2. The technique uses random sampling to build a partition-tree structure. We introduce the concept of an ε-net for an abstract set of ranges to describe the desired result of this random sampling and give necessary and sufficient conditions that a random sample is an ε-net with high probability. We illustrate the application of these ideas to other range query problems.
- BLU 85.A. Blumer, A. Ehrenfeucht, D. Haussler, M. Warmuth, "Classifying learnable geometric concepts with Lhe Vapnik-Chervonenkis dimension," Proc. 18th Syrup. on Theory of Computation, (1986) to appear. Google Scholar
Digital Library
- CHA 83.B. Chazelle, L. Guibas and D.T. Lee, "The power of geometric duality," Proc. 24th Syrup. on Foundations of Comp Sci,, 1983, 217-225.Google Scholar
- CLA 85.K. Clarkson, "A probabilistic algorithm for the post office problem," Proc. 1 ?th Syrup, an Theory of Computation, (1985) 175-185. Google ScholarDigital Library
- COL 85.R. Cole, "Partitioning point sets in 4 dimensions," Prac. Colloq. on Autom. o Lang. and Progr., (1985), 111-119, Lecture Notes in Comput. Set. 194, Springer, Berlin. Google ScholarDigital Library
- DOBa 84.D. Dobkin and H. Edelsbrunner, "Organizing points in two and three dimensions," Tech. Rep. F130, Technische Universitat Qraz, 1984. .Google Scholar
- DOBb 84.D. Dobkin, H. Edelsbrunner and F. Yao, "A 3-space partition and its applications'', manuscript.Google Scholar
- DUD 78.R.M. Dudley, "Central limit theorems for empirical measures," Ann. Prob., 8 (6)(1978)899-929.Google ScholarCross Ref
- EDL 82.H. Edelsbrunner and E. Welzl, "Halfplane range search in linear space and O(n~'~95) query time,"/nf. Proc. Let., to appear, Google ScholarDigital Library
- EDL 84.H. Edelsbrunner and F. Huber, "Dissecting sets of points in two and three dimensions," Tech. Rep. F138, Technische Universitat Graz, 1984. {EDL 85} H. Edelsbrunner, Open problem in Bu/l. ZA TCS 26 (1985).Google Scholar
- GRU 67.Branko Gruenbaum, Convex Palytopes, lnterscience (1967)Google Scholar
- VAP 71.V.N. Vapnik and A. YA. Chervonenkis, "On the uniform convergence of relative frequencies of events to their probabilities," Th. Prob. and its Appl. 16 (2) (1971) 264-280.Google ScholarCross Ref
- WEN 81.R.S. Wenocur and R.M. Dudley, "Some special Vapnik-Chervonenkis classes," Discrete Math., 31 (1891) 313- 318.Google Scholar
- WIL 82.D. Willard, "Polygon retrieval," $/~ J. Cam.put., 11 (1982) 149-165.Google ScholarCross Ref
- YAO 83.F. Yao, '~A 3-space partition and its applications," Proc. 15th Syrup. on Theory a/Computation, (1983) 258-263. Google ScholarDigital Library
- YAO 85.A. Yao and F. Yao, "A general approach to d-dimensional geometric queries," Prac. 1 ?th Syrnp. on Theory of Computation, (1985) 163-169. Google ScholarDigital Library
Index Terms
- Epsilon-nets and simplex range queries
Recommendations
ź-nets and simplex range queries
We demonstrate the existence of data structures for half-space and simplex range queries on finite point sets ind-dimensional space,d 2, with linear storage andO(n ) query time, $$\alpha = \frac{{d(d - 1)}}{{d(d - 1) + 1}} + \gamma for all \gamma > 0$$ ...
Tight lower bounds for the size of epsilon-nets
SoCG '11: Proceedings of the twenty-seventh annual symposium on Computational geometryAccording to a well known theorem of Haussler and Welzl (1987), any range space of bounded VC-dimension admits an ε-net of size O(1/ε log 1/ε). Using probabilistic techniques, Pach and Woeginger (1990) showed that there exist range spaces of VC-...
Range queries on uncertain data
Given a set P of n uncertain points on the real line, each represented by its one-dimensional probability density function, we consider the problem of building data structures on P to answer range queries of the following three types for any query ...
Comments