Covering Points by Hyperplanes and Related Problems

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F22%3A10453478" target="_blank" >RIV/00216208:11320/22:10453478 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.4230/LIPIcs.SoCG.2022.57" target="_blank" >https://doi.org/10.4230/LIPIcs.SoCG.2022.57</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.SoCG.2022.57" target="_blank" >10.4230/LIPIcs.SoCG.2022.57</a>

Result language
angličtina
Original language name
Covering Points by Hyperplanes and Related Problems
Original language description
For a set P of n points in Rd, for any d >= 2, a hyperplane h is called k-rich with respect to P if itcontains 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 Rd, d >= 3, is at least Ω(nd/kα + n/k), with asufficiently large constant of proportionality and with d <= α < 2d - 1, then there exists a (d - 2)-flatthat contains Ω(k(2d-1-α)/(d-1)) points of P. We also present upper bound constructions that giveinstances in which the above lower bound is tight. An extension of our analysis yields similar lowerbounds for k-rich spheres.
Czech name
—
Czech description
—

Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year
2022
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
Proceedings of the 38th International Symposium on Computational Geometry (SoCG 2022)
ISBN
978-3-95977-227-3
ISSN
1868-8969
e-ISSN
1868-8969
Number of pages
7
Pages from-to
1-7
Publisher name
Schloss Dagstuhl - Leibniz-Zentrum
Place of publication
Německo
Event location
Německo
Event date
Jun 7, 2022
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)