Charles Explorer logo
🇬🇧

Covering Points by Hyperplanes and Related Problems

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.