Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
428895 | Information Processing Letters | 2015 | 4 Pages |
•We prove a strong centerpoint for a class of convex polytopes with fixed orientations.•We prove a strong centerpoint for set systems with bounded intersection.•We prove a strong centerpoint for geometric set systems defined by lines and circles.
Let P be a set of n points in RdRd and FF be a family of geometric objects. We call a point x∈Px∈P a strong centerpoint of P w.r.t. FF if x is contained in all F∈FF∈F that contains more than cn points of P, where c is a fixed constant. A strong centerpoint does not exist even when FF is the family of halfspaces in the plane. We prove the existence of strong centerpoints with exact constants for convex polytopes defined by a fixed set of orientations. We also prove the existence of strong centerpoints for abstract set systems with bounded intersection.