Covering Points by Hyperplanes and Related Problems
Zuzana Patáková, Micha Sharir · SIAM Journal on Discrete Mathematics · 2025
Abstract. For a set [Formula: see text] of [Formula: see text] points in [Formula: see text], for any [Formula: see text], a hyperplane [Formula: see text] is called [Formula: see text]- rich with respect to [Formula: see text] if it contains at least [Formula: see text] points of [Formula: see text]. Answering and generalizing a question asked by Peyman Afshani, we show that if the number of [Formula: see text]-rich hyperplanes in [Formula: see text], [Formula: see text], is at least [Formula: see text], with a sufficiently large constant of proportionality and with [Formula: see text], then there exists a [Formula: see text]-flat that contains [Formula: see text] points of [Formula: see text]. 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 [Formula: see text]-rich spheres or [Formula: see text]-rich flats.