Document Open Access Logo

On Grids in Point-Line Arrangements in the Plane

Authors Mozhgan Mirzaei, Andrew Suk

PDF

File

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

Document Identifiers

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

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.

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

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.

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
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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