License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2017.12
URN: urn:nbn:de:0030-drops-71955
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7195/
Balko, Martin ;
Cibulka, Josef ;
Valtr, Pavel
Covering Lattice Points by Subspaces and Counting Point-Hyperplane Incidences
Abstract
Let d and k be integers with 1 <= k <= d-1. Let Lambda 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 the intersection of Lambda with K. In particular, our results imply that the minimum number of k-dimensional linear subspaces needed to cover the d-dimensional n * ... * n grid is at least Omega(n^(d(d-k)/(d-1)-epsilon)) and at most O(n^(d(d-k)/(d-1))), 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 k-dimensional 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 point-hyperplane 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+d-2)/((d+2)(d^2+2d-2)) - 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 Point-Hyperplane Incidences}},
booktitle = {33rd International Symposium on Computational Geometry (SoCG 2017)},
pages = {12:1--12:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-038-5},
ISSN = {1868-8969},
year = {2017},
volume = {77},
editor = {Boris Aronov and Matthew J. Katz},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7195},
URN = {urn:nbn:de:0030-drops-71955},
doi = {10.4230/LIPIcs.SoCG.2017.12},
annote = {Keywords: lattice point, covering, linear subspace, point-hyperplane incidence}
}
|
Keywords: |
|
lattice point, covering, linear subspace, point-hyperplane incidence |
|
Collection: |
|
33rd International Symposium on Computational Geometry (SoCG 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
20.06.2017 |
