On approximate range counting and depth

ABSTRACT

We improve the previous results by Aronov and Har-Peled (SODA'05) and Kaplan and Sharir (SODA'06) and present a randomized data structure of O(n) expected sizewhich can answer 3D approximate halfspace range counting queries in O(log n/k) expected time, where k is the actual value of the count. This is the first optimal method for the problem in the standard decision tree model; moreover, unlike previous methods, the new method is Las Vegas instead of Monte Carlo.In addition, we describe new results for several related problems, includingapproximate Tukey depth queries in 3D, approximate regression depthqueries in 2D, and approximate linear programming with violations inlow dimensions.

REFERENCES

• 1: P.K. Agarwal and J. Erickson. Geometric range searching and its relatives. In BChazelle, JE. Goodman, and RPollack, editors, Advances in Discrete and Computational Geometry, volume 223 of Contemporary Mathematics, pages 1--56. American Mathematical Society, Providence, RI, 1999.
• 2: 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
• 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: Marshall Bern , David Eppstein, Multivariate regression depth, Proceedings of the sixteenth annual symposium on Computational geometry, p.315-321, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong [doi>10.1145/336154.336218]
• 5: Timothy M. Chan, Fixed-dimensional linear programming queries made easy, Proceedings of the twelfth annual symposium on Computational geometry, p.284-290, May 24-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237218.237397]
• 6: T.M. Chan. Output-sensitive results on convex hulls, extreme points, and related problems. Discrete and Computational Geometry, 16:369--387, 1996.
• 7: Timothy M. Chan, Low-Dimensional Linear Programming with Violations, SIAM Journal on Computing, v.34 n.4, p.879-893, 2005 [doi>10.1137/S0097539703439404]
• 8: Timothy M. Chan, Random Sampling, Halfspace Range Reporting, and Construction of \lowercase$(\le k)$-Levels in Three Dimensions, SIAM Journal on Computing, v.30 n.2, p.561-575, 2000 [doi>10.1137/S0097539798349188]
• 9: T.M. Chan. On enumerating and selecting distances. International Journal of Computational Geometry and Applications, 11:291--304, 2001.
• 10: Timothy M. Chan, An optimal randomized algorithm for maximum Tukey depth, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 11: Bernard Chazelle , Leo J. Guibas , D. T. Lee, The power of geometric duality, BIT, v.25 n.1, p.76-90, 1985 [doi>10.1007/BF01934990]
• 12: K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989
• 13: 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 ]
• 14: H. Edelsbrunner. Algorithms in Combinatorial Geometry, volume 10 of EATCS Monographs on Theoretical Computer Science. Springer-Verlag, Heidelberg, West Germany, 1987.
• 15: H. Edelsbrunner and E. Welzl. Constructing belts in two-dimensional arrangements with applications. SIAM Journal on Computing, 15:271--284, 1986.
• 16: S. Har-Peled and M. Sharir. Relative ε-approximations in geometry. http://valis.cs.uiuc.edu/~sariel/research/papers/06/relative/, 2006. Also with B. Aronov, to appear in Proceedings of the 23rd ACM Symposium on Computational Geometry, 2007.
• 17: D. Haussler and E. Welzl. Epsilon-nets and simplex range queries. Discrete and Computational Geometry, 2:127--151, 1987.
• 18: 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]
• 19: S. Langerman and W. Steiger. The complexity of hyperplane depth in the plane. Discrete and Computational Geometry, 30(2):299--309, August 2003.
• 20: 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 ]
• 21: J. Matoušek. Range searching with efficient hierarchical cuttings. Discrete and Computational Geometry, 10(2):157--182, 1993.
• 22: J. Matoušek. On geometric optimization with few violated constraints. Discrete and Computational Geometry, 14:365--384, 1995.
• 23: K. Mulmuley. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, Englewood Cliffs, NJ, 1994.
• 24: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 25: Edgar A. Ramos, On range reporting, ray shooting and k-level construction, Proceedings of the fifteenth annual symposium on Computational geometry, p.390-399, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304993]
• 26: P.J. Rousseeuw and M. Hubert. Regression depth. Journal of American Statistical Association, 94(446):388--402, 1999.
• 27: M. Sharir, S. Smorodinsky, and G. Tardos. An improved bound for k-sets in three dimensions. Discrete and Computational Geometry, 26:195--204, 2001.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES

General Terms:
Algorithms

Keywords:
approximate counting, approximation, computational geometry, data depth