The 2nd Elbe Sandstones Geometry Workshop

I’ve been quiet for a couple of weeks because I am doing some traveling. My first stop was The 2nd Elbe Sandstones Geometry Workshop. This workshop had an interesting location — a mountain in the middle of nowhere in the Czech Republic. Here is a picture of most of the participants.

The 1st Elbe Sandstones Geometry Workshop took place 13 years ago. Following is a picture from there, in front of the same door (it is also the only picture I ever saw of Micha Sharir without a beard).

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.