Space-time tradeoffs for approximate spherical range counting

ABSTRACT

We present space-time tradeoffs for approximate spherical range counting queries. Given a set S of n data points in R^d along with a positive approximation factor ε, the goal is to preprocess the points so that, given any Euclidean ball B, we can return the number of points of any subset of S that contains all the points within a (1 - ε)-factor contraction of B, but contains no points that lie outside a (1 + ε)-factor expansion of B.In many applications of range searching it is desirable to offer a tradeoff between space and query time. We present here the first such tradeoffs for approximate range counting queries. Given 0 < ε ≤ 1/2 and a parameter γ, where 2 ≤ γ ≤ 1/ε, we show how to construct a data structure of space O(nγ^d log (1/ε)) that allows us to answer ε-approximate spherical range counting queries in time O(log(nγ) + 1/(εγ^d-1). The data structure can be built in time O(nγ^d log (n/ε)) log (1/ε)). Here n, ε, and γ are asymptotic quantities, and the dimension d is assumed to be a fixed constant.At one extreme (low space), this yields a data structure of space O(n log (1/e)) that can answer approximate range queries in time O(logn + 1/(e^d-1) which, up to a factor of O(n log (1/e) in space, matches the best known result for approximate spherical range counting queries. At the other extreme (high space), it yields a data structure of space O((n/e^d) log(1/ε)) that can answer queries in time O(logn + 1/ε). This is the fastest known query time for this problem.We also show how to adapt these data structures to the problem of computing an ε-approximation to the kth nearest neighbor, where k is any integer from 1 to n given at query time. The space bounds are identical to the range searching results, and the query time is larger only by a factor of O(1/(εγ)).Our approach is broadly based on methods developed for approximate Voronoi diagrams (AVDs), but it involves a number of significant extensions from the context of nearest neighbor searching to range searching. These include generalizing AVD node-separation properties from leaves to internal nodes of the tree and constructing efficient generator sets through a radial decomposition of space. We have also developed new arguments to analyze the time and space requirements in this more general setting.

REFERENCES

• 1: Sunil Arya , Theocharis Malamatos, Linear-size approximate voronoi diagrams, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.147-155, January 06-08, 2002, San Francisco, California
• 2: Sunil Arya , Theocharis Malamatos , David M. Mount, Space-efficient approximate Voronoi diagrams, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510011]
• 3: Sunil Arya , David M. Mount, Approximate range searching, Computational Geometry: Theory and Applications, v.17 n.3-4, p.135-152, Dec. 2000 [doi>10.1016/S0925-7721(00)00022-5 ]
• 4: Sunil Arya , David M. Mount , Nathan S. Netanyahu , Ruth Silverman , Angela Wu, An optimal algorithm for approximate nearest neighbor searching, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.573-582, January 23-25, 1994, Arlington, Virginia, United States
• 5: Sunil Arya , David M. Mount , Nathan S. Netanyahu , Ruth Silverman , Angela Y. Wu, An optimal algorithm for approximate nearest neighbor searching fixed dimensions, Journal of the ACM (JACM), v.45 n.6, p.891-923, Nov. 1998 [doi>10.1145/293347.293348]
• 6: H. Brönnimann, B. Chazelle, and J. Pach. How hard is halfspace range searching. Discrete Comput. Geom., 10:143--155, 1993.
• 7: Paul B. Callahan , S. Rao Kosaraju, A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields, Journal of the ACM (JACM), v.42 n.1, p.67-90, Jan. 1995 [doi>10.1145/200836.200853]
• 8: B. Chazelle. Lower bounds on the complexity of polytope range searching. J. Amer. Math. Soc., 2:637--666, 1989.
• 9: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 10: Michael L. Fredman , János Komlós , Endre Szemerédi, Storing a Sparse Table with 0(1) Worst Case Access Time, Journal of the ACM (JACM), v.31 n.3, p.538-544, July 1984 [doi>10.1145/828.1884]
• 11: Stefan Funke , Edgar A. Ramos, Smooth-surface reconstruction in near-linear time, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.781-790, January 06-08, 2002, San Francisco, California
• 12: S. Har-Peled, A Replacement for Voronoi Diagrams of Near Linear Size, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.94, October 14-17, 2001
• 13: Jayanth Majhi , Ravi Janardan , Michiel Smid , Prosenjit Gupta, On some geometric optimization problems in layered manufacturing, Computational Geometry: Theory and Applications, v.12 n.3-4, p.219-239, April 1999 [doi>10.1016/S0925-7721(99)00002-4 ]
• 14: J. Matoušek. Range searching with efficient hierarchical cuttings. Discrete Comput. Geom., 10(2):157--182, 1993.
• 15: J. Matoušek. On approximate geometric k-clustering. Discrete and Comput. Geometry, 24:61--84, 2000.
• 16: J. Matoušek and O. Schwarzkopf. On ray shooting in convex polytopes. Discrete Comput. Geom., 10(2):215--232, 1993.
• 17: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995