Epsilon-nets and simplex range queries

ABSTRACT

We present a new technique for half-space and simplex range query using &Ogr;(n) space and &Ogr;(na) query time, where a < d(d-1)/d(d-1) + 1 + &ggr; for all dimensions d ≥ 2 and &ggr; > 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 &egr;-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 &egr;-net with high probability. We illustrate the application of these ideas to other range query problems.

REFERENCES

• BLU 85: A Blumer , A Ehrenfeucht , D Haussler , M Warmuth, Classifying learnable geometric concepts with the Vapnik-Chervonenkis dimension, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.273-282, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12158]
• 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.
• CLA 85: K Clarkson, A probabilistic algorithm for the post office problem, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.175-184, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22165]
• COL 85: Richard Cole, Partitioning Point Sets in 4 Dimensions, Proceedings of the 12th Colloquium on Automata, Languages and Programming, p.111-119, July 15-19, 1985
• DOBa 84: D. Dobkin and H. Edelsbrunner, "Organizing points in two and three dimensions," Tech. Rep. F130, Technische Universitat Qraz, 1984. .
• DOBb 84: D. Dobkin, H. Edelsbrunner and F. Yao, "A 3-space partition and its applications'', manuscript.
• DUD 78: R.M. Dudley, "Central limit theorems for empirical measures," Ann. Prob., 8 (6)(1978)899-929.
• EDL 82: H Edelsbrunner , E Welzl, Halfplanar range search in linear space and O(n0.695) query time, Information Processing Letters, v.23 n.6, p.289-293, Dec. 3, 1986
• 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).
• GRU 67: Branko Gruenbaum, Convex Palytopes, lnterscience (1967)
• 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.
• WEN 81: R.S. Wenocur and R.M. Dudley, "Some special Vapnik-Chervonenkis classes," Discrete Math., 31 (1891) 313- 318.
• WIL 82: D. Willard, "Polygon retrieval," $/~ J. Cam.put., 11 (1982) 149-165.
• YAO 83: F. Frances Yao, A 3-space partition and its applications, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.258-263, December 1983 [doi>10.1145/800061.808755]
• YAO 85: A C Yao , F F Yao, A general approach to d-dimensional geometric queries, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.163-168, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22163]

INDEX TERMS

Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.6 Segmentation
          Subjects: Region growing, partitioning

General Terms:
Algorithms, Theory, Verification