COVERING POINTS BY HYPERPLANES AND RELATED PROBLEMS

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F25%3A10511352" target="_blank" >RIV/00216208:11320/25:10511352 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=bgcSjiXnGT" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=bgcSjiXnGT</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1137/24M1640732" target="_blank" >10.1137/24M1640732</a>

Jazyk výsledku

angličtina

Název v původním jazyce

COVERING POINTS BY HYPERPLANES AND RELATED PROBLEMS

Popis výsledku v původním jazyce

For a set P of n points in R-d, for any d &gt;= 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 &gt;= 3, is at least Omega(n(d)/k(alpha) +n/k), with a sufficiently large constant of proportionality and with d &lt;= alpha &lt;2d -1, then there exists a (d -2)-flat that contains Omega(k((2d-1-alpha)/(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 or k-rich flats.

Název v anglickém jazyce

COVERING POINTS BY HYPERPLANES AND RELATED PROBLEMS

Popis výsledku anglicky

For a set P of n points in R-d, for any d &gt;= 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 &gt;= 3, is at least Omega(n(d)/k(alpha) +n/k), with a sufficiently large constant of proportionality and with d &lt;= alpha &lt;2d -1, then there exists a (d -2)-flat that contains Omega(k((2d-1-alpha)/(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 or k-rich flats.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

<a href="/cs/project/GA25-16847S" target="_blank" >GA25-16847S: Kombinatorické struktury, spojitá matematika a jejich vliv na návrh efektivních algoritmů</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2025

Kód důvěrnosti údajů

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

Název periodika

SIAM Journal on Discrete Mathematics

ISSN

0895-4801

e-ISSN

1095-7146

Svazek periodika

39

Číslo periodika v rámci svazku

4

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

8

Strana od-do

2242-2249

Kód UT WoS článku

001636478100009

EID výsledku v databázi Scopus

2-s2.0-105024982881