Suppose we have $n$ points $P$ and $m$ circles $C$ in the plane. Let $I(P,C)=\{(p,c), p \in P, c \in C, p \in c\}.$ Then what do we know about $\max_{m,n} |I(P,C)|$?
Any references?
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communitySuppose we have $n$ points $P$ and $m$ circles $C$ in the plane. Let $I(P,C)=\{(p,c), p \in P, c \in C, p \in c\}.$ Then what do we know about $\max_{m,n} |I(P,C)|$?
Any references?
I believe these are the best known upper and lower bounds, for $m$ points and $n$ circles [reversing the OP's notation to follow published convention], established in the two cited papers: $$ I(P,C) = O^*( m^\frac{2}{3} n^\frac{2}{3} + m^\frac{6}{11} n^\frac{9}{11}) + m + n) $$ $$ I(P,C) = \Omega^*( m^\frac{2}{3} n^\frac{2}{3} + m + n) $$ (where the $*$ hides logarithmic factors).
Marcus, Adam, and Gábor Tardos. "Intersection reverse sequences and geometric applications." In International Symposium on Graph Drawing, pp. 349-359. Springer, Berlin, Heidelberg, 2004.
Pach, János, and Micha Sharir. "Geometric incidences." Contemporary Mathematics 342 (2004): 185-224.
Complexity results have been extended to $\mathbb{R}^3$:
Sharir, Micha, Adam Sheffer, and Joshua Zahl. "Improved bounds for incidences between points and circles." Combinatorics, Probability and Computing 24, no. 3 (2015): 490-520. Preliminary arXiv version.