1 Search Results for "Cibulka, Josef"

Document
DOI: 10.4230/LIPIcs.SoCG.2017.12
Covering Lattice Points by Subspaces and Counting Point-Hyperplane Incidences

Authors: Martin Balko, Josef Cibulka, and Pavel Valtr

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{balko_et_al:LIPIcs.SoCG.2017.12,
  author =	{Balko, Martin and Cibulka, Josef and Valtr, Pavel},
  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 =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.12},
  URN =		{urn:nbn:de:0030-drops-71955},
  doi =		{10.4230/LIPIcs.SoCG.2017.12},
  annote =	{Keywords: lattice point, covering, linear subspace, point-hyperplane incidence}
}
  • Refine by Author
  • 1 Balko, Martin
  • 1 Cibulka, Josef
  • 1 Valtr, Pavel

  • Refine by Classification

  • Refine by Keyword
  • 1 covering
  • 1 lattice point
  • 1 linear subspace
  • 1 point-hyperplane incidence

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2017

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 Imprint Privacy Contact