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 of points and a set of circles, both in , is
This bound was originally derived by Aronov and Sharir with instead of . 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 , for any range of . We then show that when the value of becomes close , the slightly improved bound can be obtained. This is an instance of a reoccurring theme, where the number of incidences is when , and becomes larger when is asymptotically larger than . There seems to be a common conjecture that the number of incidences between points and constant-degree curves (with no common components) is . 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 about the origin (e.g., see Chapter 37 of Hartshorne’s Geometry: Euclid and Beyond ). The inversion of any point is defined as
It is not difficult to verify that for any line that is not incident to the origin, the inversion 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 of points and a set of lines, such that . We translate the plane so that no line of is incident to the origin and no point of is the origin. Let denote the set of inversions of points of , and let denote the set of circles that are inversions of the lines of . Since the inversion of the sets preserves incidences, we have
Notice that this point-circle configuration has the additional property that every circle of is incident to the origin.
An improved bound for the case of a large . We now derive the slightly improved bound for the case where .
As our point set, we take a integer lattice. That is, we set
We denote by the set of integers between and that can be expressed as a sum of two squares. As our set of circles, we take
The size of is indeed . To obtain the cardinality of , 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 that are the sum of two squares is .
By Theorem 1, we have , and thus .
For every point and (where ), there exists an such that . That is, for every point and every pair , there exists an such that the circle of that is parametrized by is incident to the point . Since there are exactly instances of , we have