zbMATH — the first resource for mathematics

On approximate range counting and depth. (English) Zbl 1180.68124
Summary: We improve the previous results by B. Aronov and S. Har-Peled [SIAM J. Comput. 38, No. 3, 899–921 (2008; Zbl 1180.68278)] and H. Kaplan and M. Sharir [“Randomized incremental constructions of three-dimensional convex hulls and planar Voronoi diagrams, and approximate range counting”, in: Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’06, 484–493 (2006)] and present a randomized data structure of \(O(n)\) expected size which can answer 3D approximate halfspace range counting queries in \(O(\log{n\over 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, including approximate Tukey depth queries in 3D, approximate regression depth queries in 2D, and approximate linear programming with violations in low dimensions.

68P05 Data structures
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68W20 Randomized algorithms
68W25 Approximation algorithms
Full Text: DOI
[1] Afshani, P., Chan, T.M.: Optimal halfspace range reporting in three dimensions. In: Proceedings of the 20th Annual Symposium on Discrete Algorithms, pp. 180-186 (2009) · Zbl 1422.68230
[2] Agarwal, P. K.; Erickson, J.; Chazelle, B. (ed.); Goodman, J. E. (ed.); Pollack, R. (ed.), Geometric range searching and its relatives, No. 223, 1-56, (1999), Providence · Zbl 0916.68031
[3] Aronov, B., Har-Peled, S.: On approximating the depth and related problems. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 886-894 (2005). Updated version at http://valis.cs.uiuc.edu/ sariel/research/papers/04/depth/, downloaded in November 2006 · Zbl 1297.68257
[4] Arya, S.; Mount, D. M., Approximate range searching, Comput. Geom. Theory Appl., 17, 135-152, (2000) · Zbl 0968.68167
[5] Berg, M.; Schwarzkopf, O., Cuttings and applications, Int. J. Comput. Geom. Appl., 5, 343-355, (1995) · Zbl 0837.68122
[6] Bern, M., Eppstein, D.: Multivariate regression depth. In: Proceedings of the 16th Annual Symposium on Computational Geometry, pp. 315-321 (2000) · Zbl 1374.68641
[7] Chan, T.M.: Fixed-dimensional linear programming queries made easy. In: Proceedings of the 12th Annual ACM Symposium on Computational Geometry, pp. 284-290 (1996)
[8] Chan, T. M., Output-sensitive results on convex hulls, extreme points, and related problems, Discrete Comput. Geom., 16, 369-387, (1996) · Zbl 0857.68112
[9] Chan, T. M., Geometric applications of a randomized optimization technique, Discrete Comput. Geom., 22, 547-567, (1999) · Zbl 0939.68137
[10] Chan, T. M., Low-dimensional linear programming with violations, SIAM J. Comput., 34, 879-893, (2000) · Zbl 1075.68092
[11] Chan, T. M., Random sampling, halfspace range reporting, and construction of (≤\(k)\)-levels in three dimensions, SIAM J. Comput., 30, 561-575, (2000) · Zbl 0963.68207
[12] Chan, T. M., On enumerating and selecting distances, Int. J. Comput. Geom. Appl., 11, 291-304, (2001) · Zbl 1073.52506
[13] Chan, T.M.: An optimal randomized algorithm for maximum Tukey depth. In: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 430-436 (2004) · Zbl 1317.68246
[14] Chazelle, B.; Guibas, L. J.; Lee, D. T., The power of geometric duality, BIT, 25, 76-90, (1985) · Zbl 0603.68072
[15] Clarkson, K. L.; Shor, P. W., Applications of random sampling in computational geometry, II, Discrete Comput. Geom., 4, 387-421, (1989) · Zbl 0681.68060
[16] Cohen, E., Size-estimation framework with applications to transitive closure and reachability, J. Comput. Syst. Sci., 55, 441-453, (1997) · Zbl 0897.68075
[17] Edelsbrunner, H.: Algorithms in Combinatorial Geometry. EATCS Monographs on Theoretical Computer Science, vol. 10. Springer, Heidelberg (1987) · Zbl 0634.52001
[18] Edelsbrunner, H.; Welzl, E., Constructing belts in two-dimensional arrangements with applications, SIAM J. Comput., 15, 271-284, (1986) · Zbl 0613.68043
[19] Har-Peled, S., Sharir, M.: Relative \(ε\)-approximations in geometry. http://valis.cs.uiuc.edu/ sariel/research/papers/06/relative/ (2006). Also with B. Aronov, in Proceedings of the 23rd ACM Symposium on Computational Geometry, pp. 327-336 (2007) · Zbl 1221.51026
[20] Hart, S.; Sharir, M., Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes, Combinatorica, 6, 151-177, (1986) · Zbl 0636.05003
[21] Haussler, D.; Welzl, E., Epsilon-nets and simplex range queries, Discrete Comput. Geom., 2, 127-151, (1987) · Zbl 0619.68056
[22] Kaplan, H., Sharir, M.: Randomized incremental constructions of three-dimensional convex hulls and planar Voronoi diagrams, and approximate range counting. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 484-493 (2006) · Zbl 1192.68749
[23] Kaplan, H., Ramos, E., Sharir, M.: Range minima queries with respect to a random permutation, and approximate range counting. Discrete Comput. Geom. (to appear) · Zbl 1246.68105
[24] Kaplan, H., Ramos, E., Sharir, M.: The overlay of minimization diagrams in a randomized incremental construction. Manuscript (2007) · Zbl 1211.52025
[25] Langerman, S.; Steiger, W., The complexity of hyperplane depth in the plane, Discrete Comput. Geom., 30, 299-309, (2003) · Zbl 1066.68141
[26] Matoušek, J., Reporting points in halfspaces, Comput. Geom. Theory Appl., 2, 169-186, (1992) · Zbl 0772.68105
[27] Matoušek, J., Range searching with efficient hierarchical cuttings, Discrete Comput. Geom., 10, 157-182, (1993) · Zbl 0774.68101
[28] Matoušek, J., On geometric optimization with few violated constraints, Discrete Comput. Geom., 14, 365-384, (1995) · Zbl 0844.90071
[29] Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, New York (1995) · Zbl 0849.68039
[30] Mulmuley, K.: Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, Englewood Cliffs (1994)
[31] Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction. Springer, New York (1985) · Zbl 0759.68037
[32] Ramos, E.A.: On range reporting, ray shooting and \(k\)-level construction. In: Proceedings of the 14th Annual Symposium on Computational Geometry, pp. 390-399 (1999)
[33] Rousseeuw, P. J.; Hubert, M., Regression depth, J. Am. Stat. Assoc., 94, 388-402, (1999) · Zbl 1007.62060
[34] Sharir, M.; Smorodinsky, S.; Tardos, G., An improved bound for \(k\)-sets in three dimensions, Discrete Comput. Geom., 26, 195-204, (2001) · Zbl 0988.52034
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.