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?

3

$\begingroup$
$\endgroup$

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?

5

$\begingroup$

^{
Figure from Pach, Sharir, "Geometric incidences."
}

$\endgroup$

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 Mathematics342 (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 Computing24, no. 3 (2015): 490-520. Preliminary arXiv version.