An optimal generalization of the centerpoint theorem, and its extensions
Saurabh Ray, Nabil H. Mustafa · 2007
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.