Publication at Faculty of Mathematics and Physics |
2022
Abstract
For a set P of n points in R d
, for any d >= 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 R d
, d >= 3, is at least Ω(n d
/kα + n/k), with a sufficiently large constant of proportionality and with d <= α < 2d - 1, then there exists a (d - 2)-flat that contains Ω(k
(2d-1-α)/(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.