On approximate halfspace range counting and relative epsilon-approximations

ABSTRACT

The paper consists of two major parts. In the first part, we re-examine relative ε-approximations, previously studied in [12, 13, 18, 25], and their relation to certain geometric problems, most notably to approximate range counting. We give a simple constructive proof of their existence in general range spaces with finite VC dimension, and of a sharp bound on their size, close to the best known one. We then give a construction of smaller-size relative ε-approximations for range spaces that involve points and halfspaces in two and higher dimensions. The planar construction is based on a new structure--spanning trees with small relative crossing number, which we believe to be of independent interest. In the second part, we consider the approximate halfspace range-counting problem in R^d with relative error ε, and show that relative ε-approximations, combined with the shallow partitioning data structures of Matoušek, yields efficient solutions to this problem. For example, one of our data structures requires linear storage and O(n^1+δ) preprocessing time, for any δ>0, and answers a query in time O(ε^-γn^{1-1/⌊ d/2 ⌋} 2^{b log* n}), for any γ > 2/⌊ d/2⌋ the choice of γ and δ affects b and the implied constants. Several variants and extensions are also discussed.

REFERENCES

• 1: Boris Aronov , Sariel Har-Peled, On approximating the depth and related problems, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 2: B. Aronov and S. Har-Peled, On approximating the depth and related problems, manuscript, 2006. Full version of available from http://www.uiuc.edu/~sariel/papers/04/depth
• 3: B. Aronov and M. Sharir, Approximate halfspace range counting, in preparation.
• 4: Sunil Arya , Theocharis Malamatos , David M. Mount, Space-time tradeoffs for approximate spherical range counting, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 5: Sunil Arya , Theocharis Malamatos , David M. Mount, The effect of corners on the complexity of approximate range searching, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA [doi>10.1145/1137856.1137860]
• 6: B. Chazelle , E. Welzl, Quasi-optimal range searching in spaces of finite VC-dimension, Discrete & Computational Geometry, v.4 n.5, p.467-489, 1989 [doi>10.1007/BF02187743]
• 7: B. Chazelle, The Discrepancy Method: Randomness and Complexity, Cambridge University Press, New York, 2001.
• 8: B. Chazelle, The discrepancy method in computational geometry, chapter 44, in Handbook of Discrete and Computational Geometry, 2nd Edition, J.E. Goodman and J. O'Rourke, Eds., CRC Press, Boca Raton, 2004, 983--996.
• 9: Edith Cohen, Size-estimation framework with applications to transitive closure and reachability, Journal of Computer and System Sciences, v.55 n.3, p.441-453, Dec. 1997 [doi>10.1006/jcss.1997.1534]
• 10: Edith Cohen , Haim Kaplan, Spatially-decaying aggregation over a network: model and algorithms, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007647]
• 11: E. Cohen, H. Kaplan, Y. Mansour and M. Sharir, Approximations with relative errors in range spaces of finite VC dimension, manuscript, 2006.
• 12: David Haussler, Decision theoretic generalizations of the PAC model for neural net and other learning applications, Information and Computation, v.100 n.1, p.78-150, Sept. 1992 [doi>10.1016/0890-5401(92)90010-D]
• 13: D. Haussler and E. Welzl, Epsilon nets and simplex range queries, Discrete Comput. Geom. 2 (1987), 127--151.
• 14: S. Har-Peled and M. Sharir, Relative ε-approximations in geometry, Manuscript, 2006. Available from http://www.uiuc.edu/~sariel/papers/06/relative.
• 15: H. Kaplan, E. Ramos and M. Sharir, Randomized incremental construction of convex hulls and Voronoi diagrams, and approximate range counting, in preparation.
• 16: Haim Kaplan , Micha Sharir, Randomized incremental constructions of three-dimensional convex hulls and planar voronoi diagrams, and approximate range counting, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.484-493, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109611]
• 17: Yi Li , Philip M. Long , Aravind Srinivasan, Improved bounds on the sample complexity of learning, Journal of Computer and System Sciences, v.62 n.3, p.516-527, May 2001 [doi>10.1006/jcss.2000.1741]
• 18: Jiří Matoušek, Reporting points in halfspaces, Computational Geometry: Theory and Applications, v.2 n.3, p.169-186, Nov. 1992 [doi>10.1016/0925-7721(92)90006-E]
• 19: Jiří Matoušek, Efficient partition trees, Discrete & Computational Geometry, v.8 n.3, p.315-334, 1992 [doi>10.1007/BF02293051]
• 20: J. Matoušek, Geometric Discrepancy, Algorithms and Combinatorics, Vol. 18, Springer Verlag, Heidelberg, 1999.
• 21: J. Matoušek, Using the Borsuk-Ulam Theorem, Universitext, Springer-Verlag, Berlin, 2003, Lectures on topological methods in combinatorics and geometry, Written in cooperation with Anders Björner and Günter M. Ziegler.
• 22: J. Matoušek, E. Welzl and L. Wernisch, Discrepancy and approximations for bounded VC-dimension, Combinatorica 13 (1993), 455--466.
• 23: J. Pach and P.K. Agarwal, Combinatorial Geometry, Wiley Interscience, New York, 1995.
• 24: D. Pollard, Rates of uniform almost-sure convergence for empirical processes indexed by unbounded classes of functions, Manuscript, 1986.
• 25: V.N. Vapnik and A. Ya. Chervonenkis, On the uniform convergence of relative frequencies of events to their probabilities, Theory of Probability and its Applications 16 (1971), 264--280.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Object hierarchies

General Terms:
Algorithms, Theory

Keywords:
VC-dimension, approximate range queries, discrepancy, epsilon-approximations, halfspaces, partition trees, queries, range, range spaces