Point-Line Incidences

Consider the following problem: Let $P$ be a set of $n$ points and $L$ be a set of $n$ points. How to place $P$ and $L$ in the plane such that the point-line incidence pairs is maximized? More formally speaking, 

Problem 1: How to place a set $P$ of $n$ points and a set $L$ of $n$ points in the plane such that $\{(p, l): p\in P,  l\in L, \textrm{ and } p\in l\}$ has the largest cardinality?

We will only be interested in asymptotic bounds. First, observe that it is not too hard to get $\Omega(n^{3/4})$ incidences.

Consider an integer grid of size $n^{1/3}\times n^{2/3}$ and place all the points in $P$ on the grid points. Note that we have $n$ grid points. How to place the lines? Well, we consider lines on

\[ y = ax + b,\]

where $a=\{1,2,\cdots,n^{1/3}/2\}$ and $b=\{1,2,\cdots,n^{2/3}/2\}$. 

For simplicity, we assume $n^{1/3}/2$ is an integer. Then this construction gives us $n/4$ lines, each intersecting $n^{1/3}$ grid points. This already gives us $n^{1/3}\cdot n/4 = n^{4/3}/4=\Omega(n^{4/3})$ incidences. So for the remaining $3n/4$ points, we can just place them arbitrarily...

But, can we be asymptotically better? Interestingly, the answer is no by the renowned Szemerédi–Trotter theorem [ST'83]. We will prove a slightly weaker version of this theorem in this post:

Theorem 1. The number of incidences among a set $P$ of $n$ points and $L$ of $n$ lines is upper bounded by $\tilde O(n^{4/3})$.

To prove this, we use the following lemma in discrete geometry.

Lemma 1 (Cutting Lemma) [C'93]. Given a collection of $L$ lines in the plane, we can construct $O(r^2)$ triangles in the plane (possibly unbounded) such that each triangle intersects at most $n/r$ lines in $L$. 

We will also use the following tool.

Point-Line Duality. Given a point $p=(p_x,p_y)$ and a line $l=ax+b$ in the plane, the dual of $p$, denoted by $\overline{p}$ is a line $\overline{p}=p_xx-p_y$ and the dual of $l$, denoted by $\overline{l}$, is a point $\overline{l}=(a,-b)$.

A nice property of point-line duality is that it preserves incidence relations.

Lemma 2. Let $p$ be a point and $l$ be a line in the plane. If $p$ is incident to $l$, then $\overline{l}$ is incident to $\overline{p}$.

Now we can prove an upper bound for the number of incidences among points and lines in the plane.

Proof of Theorem 1. We first apply Lemma 1 to $L$ to generate $O(r^2)$ triangles such that each triangle intersects $n/r$ lines for some parameter $r$ we fix later. Then we further divide the points in each triangle to smaller sets such that each set contains at most $n/r^2$ points. Let $I(m, n)$ denote the number of incidences between $m$ points and $n$ lines. We thus have the following recurrence relation:

\[I(n, n) = O(r^2)I(n/r^2, n/r)\].

Then we apply point-line duality and by Lemma 2, the incidences are preserved. We then apply the cutting lemma again for lines from each of the $O(r^2)$ sets. This time we get

\[I(n, n) = O(r^4)I(n/r^3, n/r^3)\].

We set $r$ to be $n^c$ for some constant $c$ and it is easily verified that the recursion solves to $\tilde O(n^{4/3})$. Q.E.D.

Remark. There are several variants of the problem. For example, we can consider the asymmetric case where the number of points and that of the lines are not equal. For this problem, the result turns to be $\Theta((mn)^{2/3}+m+n)$. However, for more general problems like point-hyperplane incidences, point-circle, point-algebraic curve incidences, only partial results are known.

[C'93] Chazelle, Bernard. "Cutting hyperplanes for divide-and-conquer." Discrete & Computational Geometry 9.2 (1993): 145-158.

[ST'83] Szemerédi, Endre, and William T. Trotter. "Extremal problems in discrete geometry." Combinatorica 3 (1983): 381-392.