Helly-Type Theorems for Splitting Point Sets

Abstract

Let $0<\alpha \le 1/2$. We say that a finite point set $P$ in ${\mathbb{R}}^d$ is $\alpha$-split by a hyperplane $h$ if each of the closed half-spaces determined by $h$, contains at least $\alpha |P|$ of the points of $P$. We further say $P$ is $\alpha$-split by a $k$-dimensional flat $\tau$ if $P$ is $\alpha$-split by any hyperplane through $\tau$. In the standard notation (which coincides with Tukey depth for $k=0$), the $k$-flat $\tau$ has depth $\alpha$ with respect to $P$. We establish interesting Helly-type theorems for splitting families of finite point sets in ${\mathbb{R}}^d$. Unlike the classical sufficient Helly-type criteria for transversals to families of compact convex sets, which exist only for point and hyperplanes, our results extend to splitting families of point sets by collections of $k$-flats of arbitrary dimensionality $0\le k\le d-1$.

A preliminary version appeared in the Proceeding of SODA 2026