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|$?

  • $\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$ Apr 17 '18 at 4:34
  • $\begingroup$ @George Shakan: Thank you! It helped a lot! $\endgroup$
    – Kim
    Apr 17 '18 at 22:34

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.