On Grids in Point-Line Arrangements in the Plane
Mozhgan Mirzaei, Andrew Suk · Discrete & Computational Geometry · 2020
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 $$\mathcal {L}_a$$ and $$\mathcal {L}_b$$ be two sets of t lines in the plane and let $$P=\{\ell _a \cap \ell _b : \ell _a \in \mathcal {L}_a, \,\ell _b \in \mathcal {L}_b\}$$ be the set of intersection points between $$\mathcal {L}_a$$ and $$\mathcal {L}_b$$ . We say that $$(P, \mathcal {L}_a \cup \mathcal {L}_b)$$ forms a natural $$t\times t$$ grid if $$|P| =t^2$$ , and $${\text {conv}}P$$ does not contain the intersection point of some two lines in $$\mathcal {L}_a$$ and does not contain the intersection point of some two lines in $$\mathcal {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\times t$$ grid determines $$O(n^{{4}/{3}- \varepsilon })$$ incidences, where $$\varepsilon = \varepsilon (t)>0$$ . We also provide a construction of n points and n lines in the plane that does not contain a natural $$2 \times 2$$ grid and determines at least $$\Omega ({n^{1+{1}/{14}}})$$ incidences.