Covering points by hyperplanes and related problems

Abstract

For a set $P$ of $n$ points in ${\mathbb{R}}^d$, for any $d\ge 2$, a hyperplane $h$ is called $k$-rich with respect to $P$ if it contains at least $k$ points of $P$. Answering and generalizing a question asked by Peyman Afshani, we show that if the number of $k$-rich hyperplanes in ${\mathbb{R}}^d$, $d\ge 3$, is at least $\hat{I}\text{c◯}(n^d/k^{\hat{I}}\pm +n/k)$, with a sufficiently large constant of proportionality and with $d\le \hat{I}\pm <2d-1$, then there exists a $(d-2)$-flat that contains $\hat{I}\text{c◯}(k^{(2d-1-\hat{I}\pm )/(d-1)})$ points of $P$. We also present upper bound constructions that give instances in which the above lower bound is tight. An extension of our analysis yields similar lower bounds for $k$-rich spheres or $k$-rich flats.

8 pages