Partition trees for triangle counting and other range searching problems

ABSTRACT

The range searching problems which allow partition trees where every query enters only a sublinear number of nodes are characterized as those with finite Vapnik - Chervonenk is dimension.The concrete combinatorial bounds obtained imply—among others — that every set of n points in the planecan be stored in an &Ogr;(n) space data structure which allows triangle counting queries in &Ogr;(√n· log3n) time, andcan be stored in an &Ogr;(n · log n) space data structure which allows disk counting queries in &Ogr;(√n· log3n) time; the preprocessing time for the data structures is polynomial. Recent results by Chazelle entail that these bounds for space and query time are optimal up to polylog — factors.

REFERENCES

• AHWW: N. Alon , D. Haussler , E. Welzl, Partitioning and geometric embedding of range spaces of finite Vapnik-Chervonenkis dimension, Proceedings of the third annual symposium on Computational geometry, p.331-340, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41994]
• As: Assouad P., Densit~ et dimension, Ann lnst Fourier (Grenoble) 33 (1983) 233-282.
• Ch: Chazelle B., Polytope range searching and integral geometry, in "Proceedings of the 28th Symposium on Foundations of Computer Science", to appear, 1987,
• Du1: Dudley R.M., Central limit theorems for empirical measures, The Annals of Probability 6 (1978) 89~-929.
• Du2: Dudley R.M., Balls in R'" do not cut all subsets of k+2 points, Adu in Math 31 (1979) 306-309.
• Ed: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• EW: 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
• HW: Haussler D. and Welzl E., c-nets and simplex range queries, Discrete Comput Geom 2 (1987) 127-151.
• Me: Kurt Mehlhorn, Data structures and algorithms 3: multi-dimensional searching and computational geometry, Springer-Verlag New York, Inc., New York, NY, 1984
• PS: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• Sa: Sauer N., On the density of families of sets, J Combin Theory Set A 13 (1972) 145-147.
• VC: Vapnik V.N. and Chervonenkis A. Ya., On the uniform convergence of relative frequencies of events to their probabilities, Theory Probab Appl 16 (1971) 264-280.
• WW: Welzl E. and WSginger G., On shatter functions of range spaces, manuscript, 1987.
• Wi: Willard D., Polygon retrieval, SIAM J Comput 11 (1982) 149-165.

INDEX TERMS

Primary 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

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Arrays; Trees
  E.5 FILES
      Subjects: Sorting/searching

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.7 Ordinary Differential Equations
          Subjects: Boundary value problems
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms
      G.2.2 Graph Theory
          Subjects: Trees

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.6 Segmentation
          Subjects: Region growing, partitioning

General Terms:
Algorithms, Measurement, Performance, Theory