An optimal extension of the centerpoint theorem

摘要

We prove an optimal extension 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 all convex sets containing more than in points of P. We further prove that this bound is tight. We get this bound as part of a more general procedure for finding small number of points hitting convex sets over P, yielding several improvements over previous results.