2026-07-23T03:47:59Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10454 2024-03-06T10:46:01Z ddc:004 open_access

On Grids in Point-Line Arrangements in the Plane Mirzaei, Mozhgan Suk, Andrew Szemerédi-Trotter Theorem Grids Sidon sets 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mozhgan Mirzaei and Andrew Suk 2019 Is Part Of LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2019.50 urn:nbn:de:0030-drops-104541 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.50 eng https://creativecommons.org/licenses/by/3.0/legalcode