On Strong Centerpoints

Abstract

Let $P$ be a set of $n$ points in ${\mathbb{R}}^d$ and $\mathcal{F}$ be a family of geometric objects. We call a point $x\in P$ a strong centerpoint of $P$ w.r.t $\mathcal{F}$ if $x$ is contained in all $F\in \mathcal{F}$ that contains more than $cn$ points from $P$, where $c$ is a fixed constant. A strong centerpoint does not exist even when $\mathcal{F}$ 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.