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|$?
2
-
$\begingroup$ I would recommend reading chapter 8 of tao and vus book on additive combinatorics which will answer this question and the other question you recently posted. $\endgroup$– George ShakanCommented Apr 17, 2018 at 4:34
-
$\begingroup$ @George Shakan: Thank you! It helped a lot! $\endgroup$– KimCommented Apr 17, 2018 at 22:34
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
