Helly-Type Theorems for Splitting Point Sets

Let 0 < α ≤ 1/2. We say that a finite point set P in R d is α-split by a hyperplane h if each of the closed half-spaces determined by h, contains at least α|P | of the points of P . We further say P is α-split by a k-dimensional flat τ if P is α-split by any hyperplane through τ . In the standard notation (which coincides with Tukey depth for k = 0), the k-flat τ has depth α with respect to P .

We establish interesting Helly-type theorems for splitting families of finite point sets in 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 ≤ k ≤ d -1.