2026-07-21T23:35:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16065 2024-03-06T10:56:52Z ddc:004 open_access

Covering Points by Hyperplanes and Related Problems Patáková, Zuzana Sharir, Micha Rich hyperplanes Incidences Covering points by hyperplanes For a set P of n points in ℝ^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 ℝ^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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Zuzana Patáková and Micha Sharir 2022 Is Part Of LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2022.57 urn:nbn:de:0030-drops-160652 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.57 eng https://creativecommons.org/licenses/by/4.0/legalcode