An optimal generalization of the centerpoint theorem, and its extensions

ABSTRACT

We prove an optimal generalization of the centerpoint theorem: given a set P of n points in the plane, there exist two points (not necessarily among input points) that hit allconvex objects containingmore than 4n/7 points of P. We further prove that this bound is tight. We get this bound as part of a more general procedure forfinding small number of points hitting convex sets over P, yieldingseveral improvements over previous results.

REFERENCES

• 1: Noga Alon, Imre Bárány, Zoltán Füredi, and Daniel J. Kleitman. Point selections and weak e-nets for convex hulls. Combinatorics, Probability & Computing, 1:189--200, 1992.
• 2: B. Aronov, F. Aurenhammer, F. Hurtado, S. Langerman, D. Rappaport, S. Smorodinsky, and C. Seara. Small weak epsilon nets. In Proc. 17th Canadian Conference on Computational Geometry, 2005.
• 3: Bernard Chazelle , Herbert Edelsbrunner , Michelangelo Grigni , Leonidas Guibas , Micha Sharir , Emo Welzl, Improved bounds on weak &egr;-nets for convex sets, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.495-504, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167222]
• 4: Kenneth L. Clarkson, David Eppstein, Gary L. Miller, Carl Sturtivant, and Shang-Hua Teng. Approximating center points with iterative radon points. Int. J. Comput. Geometry Appl, 6(3):357--377, 1996.
• 5: D.L. Donoho and M. Gasko. Breakdown properties of location estimates based on halfspace depth and projected outlyingness. The Annals of Statistics, 20:1803--1827, 1994.
• 6: Jirí Matousek. Lectures in Discrete Geometry. Springer-Verlag, New York, NY, 2002.
• 7: Jirí Matousek , Uli Wagner, New Constructions of Weak ε-Nets, Discrete & Computational Geometry, v.32 n.2, p.195-206, July 2004 [doi>10.1007/s00454-004-1116-4]
• 8: G. Miller, S. Teng, WThurston, and S.A. Vavasis. Automatic mesh partitioning. Workshop on Sparse Matrix Computations: Graph Theory Issues and Algorithms, 1993.
• 9: Gary L. Miller , Shang-Hua Teng , William Thurston , Stephen A. Vavasis, Separators for sphere-packings and nearest neighbor graphs, Journal of the ACM (JACM), v.44 n.1, p.1-29, Jan. 1997 [doi>10.1145/256292.256294]
• 10: Janos Pach and Pankaj K. Agarwal. Combinatorial Geometry. John Wiley & Sons, New York, NY, 1995.
• 11: F. Frances Yao, A 3-space partition and its applications, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.258-263, December 1983 [doi>10.1145/800061.808755]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Theory

Keywords:
centerpoint theorem, combinatorial geometry, discrete geometry, extremal methods, hitting convex sets, weak ε-nets