Balko, Martin ;
Cibulka, Josef ;
Valtr, Pavel
Covering Lattice Points by Subspaces and Counting PointHyperplane Incidences
Abstract
Let d and k be integers with 1 <= k <= d1. Let Lambda be a ddimensional lattice and let K be a ddimensional compact convex body symmetric about the origin. We provide estimates for the minimum number of kdimensional linear subspaces needed to cover all points in the intersection of Lambda with K. In particular, our results imply that the minimum number of kdimensional linear subspaces needed to cover the ddimensional n * ... * n grid is at least Omega(n^(d(dk)/(d1)epsilon)) and at most O(n^(d(dk)/(d1))), where epsilon > 0 is an arbitrarily small constant. This nearly settles a problem mentioned in the book of Brass, Moser, and Pach. We also find tight bounds for the minimum number of kdimensional affine subspaces needed to cover the intersection of Lambda with K.
We use these new results to improve the best known lower bound for the maximum number of pointhyperplane incidences by Brass and Knauer. For d > =3 and epsilon in (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 R^d and an arrangement of m hyperplanes in R^d with no K_(r,r) in their incidence graph and with at least Omega((mn)^(1(2d+3)/((d+2)(d+3))  epsilon)) incidences if d is odd and Omega((mn)^(1(2d^2+d2)/((d+2)(d^2+2d2))  epsilon)) incidences if d is even.
BibTeX  Entry
@InProceedings{balko_et_al:LIPIcs:2017:7195,
author = {Martin Balko and Josef Cibulka and Pavel Valtr},
title = {{Covering Lattice Points by Subspaces and Counting PointHyperplane Incidences}},
booktitle = {33rd International Symposium on Computational Geometry (SoCG 2017)},
pages = {12:112:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770385},
ISSN = {18688969},
year = {2017},
volume = {77},
editor = {Boris Aronov and Matthew J. Katz},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7195},
URN = {urn:nbn:de:0030drops71955},
doi = {10.4230/LIPIcs.SoCG.2017.12},
annote = {Keywords: lattice point, covering, linear subspace, pointhyperplane incidence}
}
20.06.2017
Keywords: 

lattice point, covering, linear subspace, pointhyperplane incidence 
Seminar: 

33rd International Symposium on Computational Geometry (SoCG 2017)

Issue date: 

2017 
Date of publication: 

20.06.2017 