Document Open Access Logo

On Grids in Point-Line Arrangements in the Plane

Authors Mozhgan Mirzaei, Andrew Suk

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2019.50.pdf
  • Filesize: 0.57 MB
  • 11 pages

Document Identifiers

Author Details

Mozhgan Mirzaei
  • Department of Mathematics, University of California at San Diego, La Jolla, CA, 92093 USA
Andrew Suk
  • Department of Mathematics, University of California at San Diego, La Jolla, CA, 92093 USA

Funding

  • Mirzaei, Mozhgan: Supported by NSF grant DMS-1800746.
  • Suk, Andrew: Supported by an NSF CAREER award and an Alfred Sloan Fellowship.

Cite As Get BibTex

Mozhgan Mirzaei and Andrew Suk. On Grids in Point-Line Arrangements in the Plane. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 50:1-50:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.SoCG.2019.50

Abstract

The famous Szemerédi-Trotter theorem states that any arrangement of n points and n lines in the plane determines O(n^{4/3}) incidences, and this bound is tight. In this paper, we prove the following Turán-type result for point-line incidence. Let L_a and L_b be two sets of t lines in the plane and let P={l_a cap l_b : l_a in L_a, l_b in L_b} be the set of intersection points between L_a and L_b. We say that (P, L_a cup L_b) forms a natural t x t grid if |P| =t^2, and conv(P) does not contain the intersection point of some two lines in L_a and does not contain the intersection point of some two lines in L_b. For fixed t > 1, we show that any arrangement of n points and n lines in the plane that does not contain a natural t x t grid determines O(n^{4/3- epsilon}) incidences, where epsilon = epsilon(t)>0. We also provide a construction of n points and n lines in the plane that does not contain a natural 2 x 2 grid and determines at least Omega(n^{1+1/14}) incidences.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatoric problems
Keywords
  • Szemerédi-Trotter Theorem
  • Grids
  • Sidon sets

Metrics

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

References

  1. Boris Aronov, Paul Erdős, Wayne Goddard, Daniel Kleitman, Michael Klugerman, János Pach, and Leonard J. Schulman. Crossing families. Combinatorica, 14(2):127-134, 1994. Google Scholar
  2. Peter Brass, William O.J. Moser, and János Pach. Research problems in discrete geometry. Springer Science &Business Media, 2006. Google Scholar
  3. Boris Bukh and Alfredo Hubard. Space crossing numbers. Combin. Probab. Comput., 21(3):358-373, 2012. Google Scholar
  4. Javier Cilleruelo and Craig Timmons. k-Fold Sidon Sets. Electron. J. Combin., 21(4):P4-12, 2014. Google Scholar
  5. Robert P Dilworth. A decomposition theorem for partially ordered sets. Ann. of Math., pages 161-166, 1950. Google Scholar
  6. Vida Dujmović and Stefan Langerman. A Center Transversal Theorem for Hyperplanes and Applications to Graph Drawing. Discrete Comput. Geom., 49(1):74-88, January 2013. URL: http://dx.doi.org/10.1007/s00454-012-9464-y.
  7. Paul Erdös and Pál Turán. On a problem of Sidon in additive number theory, and on some related problems. J. Lond. Math. Soc. (2), 1(4):212-215, 1941. Google Scholar
  8. Jacob Fox, Mikhail Gromov, Vincent Lafforgue, Assaf Naor, and János Pach. Overlap properties of geometric expanders. J. Reine Angew. Math., 2012(671):49-83, 2012. Google Scholar
  9. Jacob Fox, János Pach, and Andrew Suk. A polynomial regularity lemma for semialgebraic hypergraphs and its applications in geometry and property testing. SIAM J. Comput., 45(6):2199-2223, 2016. Google Scholar
  10. Tamás Kovári, Vera Sós, and Pál Turán. On a problem of K. Zarankiewicz. 3(1):50-57, 1954. Google Scholar
  11. Felix Lazebnik and Jacques Verstraëte. On hypergraphs of girth five. Electron. J. Combin., 10:1-25, 2003. Google Scholar
  12. Jiří Matoušek. Efficient partition trees. Discrete Comput. Geom., 8(3):315-334, 1992. Google Scholar
  13. János Pach and Pankaj K Agarwal. Combinatorial geometry, volume 37. John Wiley &Sons, 2011. Google Scholar
  14. Imre Z Ruzsa. Solving a linear equation in a set of integers I. Acta Arith., 65(3):259-282, 1993. Google Scholar
  15. József Solymosi. Dense arrangements are locally very dense I. SIAM J. Discrete Math., 20(3):623-627, 2006. Google Scholar
  16. Endre Szemerédi and William T. Trotter. Extremal problems in discrete geometry. Combinatorica, 3(3-4):381-392, 1983. Google Scholar
  17. Jacques Verstraëte. Extremal problems for cycles in graphs. In Recent Trends in Combinatorics, pages 83-116. Springer, 2016. 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