Let $P$ be a set of $n$ points and let $C$ be a set of $n$ unit circles, both in $\mathbb{R}^2.$ The maximum number of incidences between P and C is $O(n^{\frac{4}{3}}).$
Is there any bound known for incidences between P and C when $|P| \neq |C|$?
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communityLet $P$ be a set of $n$ points and let $C$ be a set of $n$ unit circles, both in $\mathbb{R}^2.$ The maximum number of incidences between P and C is $O(n^{\frac{4}{3}}).$
Is there any bound known for incidences between P and C when $|P| \neq |C|$?
Let $I(P,C)$ be the number of incidences in your point-circle configuration. One has $$I(P,C) \ll |P|^{2/3} |C|^{2/3} + |C| + |P|,$$ by the Szemeredi-Trotter theorem. Note that while this is optimal for lines, this is not necessarily optimal for circles. Variants of the grid construction, as in Chapter 2 of these notes are still the best known examples, but they give less than $C_{\epsilon} n^{1 + \epsilon}$ incidences where $n = |P| = |C|$. For more references, check out the suggested reading for an upcoming conference.