Covering Lattice Points by Subspaces and Counting Point-Hyperplane Incidences

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F19%3A10403067" target="_blank" >RIV/00216208:11320/19:10403067 - isvavai.cz</a>

Výsledek na webu

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

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s00454-018-9970-7" target="_blank" >10.1007/s00454-018-9970-7</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Covering Lattice Points by Subspaces and Counting Point-Hyperplane Incidences

Popis výsledku v původním jazyce

Let d and k be integers with 1kd-1. Let be a d-dimensional lattice and let K be a d-dimensional compact convex body symmetric about the origin. We provide estimates for the minimum number of k-dimensional linear subspaces needed to cover all points in K. In particular, our results imply that the minimum number of k-dimensional linear subspaces needed to cover the d-dimensional nxxn grid is at least (nd(d-k)/(d-1)-epsilon) and at most O(nd(d-k)/(d-1)), where epsilon&gt;0 is an arbitrarily small constant. This nearly settles a problem mentioned in the book by Brass et al. (Research problems in discrete geometry, Springer, New York, 2005). We also find tight bounds for the minimum number of k-dimensional affine subspaces needed to cover K. We use these new results to improve the best known lower bound for the maximum number of point-hyperplane incidences by Brass and Knauer (Comput Geom 25(1-2):13-20, 2003). For d3 and epsilon(0,1), we show that there is an integer r=r(d,epsilon) such that for all positive integers n,m the following statement is true. There is a set of n points in Rd and an arrangement of m hyperplanes in Rd with no Kr,r in their incidence graph and with at least ((mn)1-(2d+3)/((d+2)(d+3))-epsilon) incidences if d is odd and ((mn)1-(2d2+d-2)/((d+2)(d2+2d-2))-epsilon) incidences if d is even.

Název v anglickém jazyce

Covering Lattice Points by Subspaces and Counting Point-Hyperplane Incidences

Popis výsledku anglicky

Let d and k be integers with 1kd-1. Let be a d-dimensional lattice and let K be a d-dimensional compact convex body symmetric about the origin. We provide estimates for the minimum number of k-dimensional linear subspaces needed to cover all points in K. In particular, our results imply that the minimum number of k-dimensional linear subspaces needed to cover the d-dimensional nxxn grid is at least (nd(d-k)/(d-1)-epsilon) and at most O(nd(d-k)/(d-1)), where epsilon&gt;0 is an arbitrarily small constant. This nearly settles a problem mentioned in the book by Brass et al. (Research problems in discrete geometry, Springer, New York, 2005). We also find tight bounds for the minimum number of k-dimensional affine subspaces needed to cover K. We use these new results to improve the best known lower bound for the maximum number of point-hyperplane incidences by Brass and Knauer (Comput Geom 25(1-2):13-20, 2003). For d3 and epsilon(0,1), we show that there is an integer r=r(d,epsilon) such that for all positive integers n,m the following statement is true. There is a set of n points in Rd and an arrangement of m hyperplanes in Rd with no Kr,r in their incidence graph and with at least ((mn)1-(2d+3)/((d+2)(d+3))-epsilon) incidences if d is odd and ((mn)1-(2d2+d-2)/((d+2)(d2+2d-2))-epsilon) incidences if d is even.

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/GA14-14179S" target="_blank" >GA14-14179S: Algoritmické, strukturální a složitostní aspekty konfigurací v rovině</a><br>

Návaznosti

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

Rok uplatnění

2019

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

Discrete and Computational Geometry

ISSN

0179-5376

e-ISSN

—

Svazek periodika

61

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

30

Strana od-do

325-354

Kód UT WoS článku

000456720300006

EID výsledku v databázi Scopus

2-s2.0-85041829923