Incidences: Lower Bounds (part 3)

This is the third in my series of posts concerning lower bound for incidence problems (see the previous post here).

After discussing incidences with lines in the first two posts, we now move to consider incidences with circles. The best known upper bound for the number of incidences between a set $\cal P$ of $m$ points and a set $\cal C$ of $n$ circles, both in ${\mathbb R}^2$, is

$I({\cal P},{\cal C}) = O(m^{2/3}n^{2/3} + m^{6/11}n^{9/11}\log^{2/11}(m^3/n)+m+n).$

This bound was originally derived by Aronov and Sharir with $m^{6/11+\varepsilon}$ instead of $m^{6/11}$. The slightly improved bound is obtained by combining their work with later results of Agarwal et al. and of Marcus and Tardos.

We first describe a simple method for constructing a point-circle configuration with $I({\cal P},{\cal C}) = \Theta(m^{2/3}n^{2/3}+m+n)$, for any range of $m,n$. We then show that when the value of $n$ becomes close $m^2$, the slightly improved bound $\Theta(m^{2/3}n^{2/3}\log^{1/3} m)$ can be obtained. This is an instance of a reoccurring theme, where the number of incidences is $\Theta(m^{2/3}n^{2/3})$ when $n=\Theta(m)$, and becomes larger when $n$ is asymptotically larger than $m$. There seems to be a common conjecture that the number of incidences between $n$ points and $n$ constant-degree curves (with no common components) is $O(n^{4/3})$. However, it is not so clear what should happen when the number of curves is significantly larger than the number of points. I plan to present more impressive instances of this phenomenon in a future post.

A general bound. We recall the inversion transformation $\tau:{\mathbb R}^2 \to {\mathbb R}^2$ about the origin (e.g., see Chapter 37 of Hartshorne’s Geometry: Euclid and Beyond ). The inversion of any point $p=(x,y)\neq (0,0)$ is defined as

$\tau(p)= \left(\frac{x}{x^2+y^2}, \frac{y}{x^2+y^2}\right).$

It is not difficult to verify that for any line $\ell$ that is not incident to the origin, the inversion $\tau(\ell)$ is a circle that is incident to the origin. The inversion transformation has several additional nice properties, but we will not require these here.

An inversion of a Vermeer painting, taken from here. Notice that the window, which is originally a segment of a line that is not incident to the origin, is inverted to an arc of a circle that is incident to the origin.

Consider any of the point-line configurations that were described in the first two posts. That is, we have a set $\cal P$ of $m$ points and a set $\cal L$ of $n$ lines, such that $I({\cal P},{\cal L})=\Theta(m^{2/3}n^{2/3}+m+n)$. We translate the plane so that no line of $\cal L$ is incident to the origin and no point of $\cal P$ is the origin. Let ${\cal P}' = \tau({\cal P})$ denote the set of inversions of points of ${\cal P}$, and let ${\cal C}= \tau({\cal L})$ denote the set of circles that are inversions of the lines of $\cal L$. Since the inversion of the sets preserves incidences, we have

$I({\cal P},{\cal C}) = I({\cal P},{\cal L})= \Theta(m^{2/3}n^{2/3}+m+n).$

Notice that this point-circle configuration has the additional property that every circle of ${\cal C}$ is incident to the origin.

An improved bound for the case of a large $n$. We now derive the slightly improved bound $\Theta(m^{2/3}n^{2/3}\log^{1/3} m)$ for the case where $n = \Theta(m^2/\sqrt{\log m})$.

As our point set, we take a $\sqrt{m}\times\sqrt{m}$ integer lattice. That is, we set

${\cal P} = \left\{ (i,j) | 1 \le i,j \le \sqrt{m} \right\}.$

We denote by $R$ the set of integers between $1$ and $2m$ that can be expressed as a sum of two squares. As our set of circles, we take

${\cal C} = \left\{ (x-a)^2 + (y-b)^2 = r \ | \ 1 \le a,b \le \sqrt{m}, \quad r\in R \ \right\}.$

The size of $\cal P$ is indeed $m$. To obtain the cardinality of $\cal C$, we recall a theorem from number theory by Landau and Ramanujan (which is starting to appear rather frequently in my posts).

Theorem 1 (Landau-Ramanujan). The number of positive integers smaller than $n$ that are the sum of two squares is $\Theta(n/\sqrt{\log n})$.

By Theorem 1, we have $|R|=\Theta(m/\sqrt{\log m})$, and thus $n = |{\cal C}| = \Theta(m^2/\sqrt{\log m})$.

For every point $(i,j)\in {\cal P}$ and $(a,b)\neq (i,j)$ (where $1\le a,b \le \sqrt{m}$), there exists an $r\in R$ such that $(i-a)^2+(j-b)^2 = r$. That is, for every point $p\in {\cal P}$ and every pair $(a,b)\neq p$, there exists an $r\in R$ such that the circle of ${\cal C}$ that is parametrized by $(a,b,r)$ is incident to the point $p$. Since there are exactly $m$ instances of $(a,b)=(i,j)$, we have

$I({\cal P}, {\cal C}) = m^2 - m = \Theta(m^{2/3}n^{2/3}\log^{1/3} m).$