Skip to main content
Added figure.
Source Link
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958

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.


          [![CircsPts][1]][1]
          Figure from Pach, Sharir, "Geometric incidences."

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.

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.

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.


          [![CircsPts][1]][1]
          Figure from Pach, Sharir, "Geometric incidences."

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.

added 8 characters in body
Source Link
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958

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.

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.

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.

Source Link
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958

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.