On approximating the depth and related problems

ABSTRACT

In this paper, we study the problem of finding a disk covering the largest number of red points, while avoiding all the blue points. We reduce it to the question of finding a deepest point in an arrangement of pseudodisks and provide a near-linear expected-time randomized approximation algorithm for this problem. As an application of our techniques, we show how to solve linear programming with violations approximately. We also prove that approximate range counting has roughly the same time and space complexity as answering emptiness range queries.

REFERENCES

• 1: Martin M. Anthony , Peter Bartlett, Learning in Neural Networks: Theoretical Foundations, Cambridge University Press, New York, NY, 1999
• 2: {AE98} P. K. Agarwal and J. Erickson. Geometric range searching and its relatives. In B. Chazelle, J. E. Goodman, and R. Pollack, editors, Advances in Discrete and Computational Geometry. AMS Press, Providence, RI. 1998.
• 3: Pankaj K. Agarwal , Alon Efrat , Micha Sharir, Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications, SIAM Journal on Computing, v.29 n.3, p.912-953, Dec. 1999 to Jan. 2000 [doi>10.1137/S0097539795295936]
• 4: 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 ]
• 5: {BCP93} H. Brönnimann, B. Chazelle, and J. Pach. How hard is halfspace range searching. Discrete Comput. Geom., 10:143--155, 1993.
• 6: 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]
• 7: Timothy M. Chan, Low-Dimensional Linear Programming with Violations, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.570, November 16-19, 2002
• 8: 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
• 9: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 10: {DK85} D. P. Dobkin and D. G. Kirkpatrick. A linear algorithm for determining the separation of convex polyhedra. J. Algorithms, 6:381--392, 1985.
• 11: David P. Dobkin , David G. Kirkpatrick, Determining the Separation of Preprocessed Polyhedra - A Unified Approach, Proceedings of the 17th International Colloquium on Automata, Languages and Programming, p.400-413, July 16-20, 1990
• 12: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 13: Alon Efrat, The complexity of the union of (&agr;, &bgr;)-covered objects, Proceedings of the fifteenth annual symposium on Computational geometry, p.134-142, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304958]
• 14: Anka Gajentaan , Mark H. Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry: Theory and Applications, v.5 n.3, p.165-185, Oct. 1995 [doi>10.1016/0925-7721(95)00022-2 ]
• 15: Sariel Har-Peled , Piotr Indyk, When crossings count — approximating the minimum spanning tree, Proceedings of the sixteenth annual symposium on Computational geometry, p.166-175, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong [doi>10.1145/336154.336197]
• 16: Sariel Har-Peled , Yusu Wang, Shape Fitting with Outliers, SIAM Journal on Computing, v.33 n.2, p.269-285, 2004 [doi>10.1137/S0097539703427963]
• 17: Piotr Indyk , Rajeev Motwani, Approximate nearest neighbors: towards removing the curse of dimensionality, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.604-613, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276876]
• 18: Piotr Indyk , Rajeev Motwani, High-dimensional computational geometry, 2001
• 19: Klara Kedem , Ron Livne , János Pach , Micha Sharir, On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles, Discrete & Computational Geometry, v.1 n.1, p.59-71, 1986 [doi>10.1007/BF02187683]
• 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: {Mat93} J. Matoušek. Range searching with efficient hierarchical cuttings. Discrete Comput. Geom., 10(2):157--182, 1993.
• 22: {Mat95} J. Matoušek. On geometric optimization with few violated constraints. Discrete Comput. Geom., 14:365--384, 1995.
• 23: Jiří Matoušek , Nathaly Miller , Micha Sharir , Shmuel Sifrony , János Pach , Emo Welzl, Fat triangles determine linearly many holes, Proceedings of the 32nd annual symposium on Foundations of computer science, p.49-58, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185347]
• 24: Ketan Mulmuley, On levels in arrangements and Voronoi diagrams, Discrete & Computational Geometry, v.6 n.4, p.307-338, 1991
• 25: {Sha91} M. Sharir. On k-sets in arrangements of curves and surfaces. Discrete Comput. Geom., 6:593--613, 1991.
• 26: Micha Sharir, The Clarkson–Shor Technique Revisited and Extended, Combinatorics, Probability and Computing, v.12 n.2, p.191-201, March 2003 [doi>10.1017/S0963548302005527]