Document Open Access Logo

Covering Lattice Points by Subspaces and Counting Point-Hyperplane Incidences

Authors Martin Balko, Josef Cibulka, Pavel Valtr

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2017.12.pdf
  • Filesize: 0.53 MB
  • 16 pages

Document Identifiers

Author Details

Martin Balko
Josef Cibulka
Pavel Valtr

Cite As Get BibTex

Martin Balko, Josef Cibulka, and Pavel Valtr. Covering Lattice Points by Subspaces and Counting Point-Hyperplane Incidences. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.SoCG.2017.12

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.

Subject Classification

Keywords
  • lattice point
  • covering
  • linear subspace
  • point-hyperplane incidence

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. E. Ackerman. On topological graphs with at most four crossings per edge. http://arxiv.org/abs/1509.01932, 2015.
  2. R. Apfelbaum and M. Sharir. Large complete bipartite subgraphs in incidence graphs of points and hyperplanes. SIAM J. Discrete Math., 21(3):707-725, 2007. Google Scholar
  3. M. Balko, J. Cibulka, and P. Valtr. Covering lattice points by subspaces and counting point-hyperplane incidences. http://arxiv.org/abs/1703.04767, 2017.
  4. W. Banaszczyk. New bounds in some transference theorems in the geometry of numbers. Math. Ann., 296(4):625-635, 1993. Google Scholar
  5. I. Bárány, G. Harcos, J. Pach, and G. Tardos. Covering lattice points by subspaces. Period. Math. Hungar., 43(1-2):93-103, 2001. Google Scholar
  6. P. Brass and C. Knauer. On counting point-hyperplane incidences. Comput. Geom., 25(1-2):13-20, 2003. Google Scholar
  7. P. Brass, W. Moser, and J. Pach. Research problems in discrete geometry. Springer, New York, 2005. Google Scholar
  8. B. Chazelle. Cutting hyperplanes for Divide-and-Conquer. Discrete Comput. Geom., 9(2):145-158, 1993. Google Scholar
  9. P. Erdős. On sets of distances of n points. Amer. Math. Monthly, 53:248-250, 1946. Google Scholar
  10. J. Erickson. New lower bounds for hopcroft’s problem. Discrete Comput. Geom., 16(4):389-418, 1996. Google Scholar
  11. J. Fox, J. Pach, A. Sheffer, and A. Suk. A semi-algebraic version of Zarankiewicz’s problem. http://arxiv.org/abs/1407.5705, 2014.
  12. T. Hagerup and C. Rüb. A guided tour of Chernoff bounds. Inform. Process. Lett., 33(6):305-308, 1990. Google Scholar
  13. M. Henk. Successive minima and lattice points. Rend. Circ. Mat. Palermo (2) Suppl., 70(I):377-384, 2002. Google Scholar
  14. F. John. Extremum problems with inequalities as subsidiary conditions. In Studies and Essays, presented to R. Courant on his 60th birthday, January 8, 1948, pages 187-204. Interscience Publ., New York, 1948. Google Scholar
  15. H. Lefmann. Extensions of the No-Three-In-Line Problem. https://www.tu-chemnitz.de/informatik/ThIS/downloads/publications/lefmann_no_three_submitted.pdf, 2012.
  16. K. Mahler. Ein Übertragungsprinzip für konvexe Körper. Časopis Pěst. Mat. Fys., 68:93-102, 1939. Google Scholar
  17. J. Matoušek. Lectures on Discrete Geometry, volume 212 of Graduate Texts in Mathematics. Springer-Verlag, New York, 2002. Google Scholar
  18. H. Minkowski. Geometrie der Zahlen. Leipzig, Teubner, 1910. Google Scholar
  19. János Pach and Géza Tóth. Graphs drawn with few crossings per edge. Combinatorica, 17:427-439, 1997. Google Scholar
  20. K. F. Roth. On a problem of Heilbronn. J. London Math. Soc., 26:198-204, 1951. Google Scholar
  21. Adam Sheffer. Lower bounds for incidences with hypersurfaces. Discrete Anal., 2016. Paper No. 16, 14. Google Scholar
  22. C. L. Siegel and K. Chandrasekharan. Lectures on the geometry of numbers. Springer-Verlag, Berlin, 1989. Google Scholar
  23. E. Szemerédi and W. T. Trotter Jr. Extremal problems in discrete geometry. Combinatorica, 3(3-4):381-392, 1983. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact