Incidences between points and circles in three and higher dimensions
Boris S. Aronov, Vladlen Koltun, Micha Sharir · 2002
(MATH) We show that the number of incidences between m distinct points and n distinct circles in $\reals^3$ is O(m 4/7 n 17/21+m 2/3 n 2/3+m+n); the bound is optimal for m n 3/2. This result extends recent work on point-circle incidences in the plane, but its proof requires a different analysis. The bound improves upon a previous bound, noted by Akutsu et al. [2] and by Agarwal and Sharir [1], but it is not as sharp (when m is small) as the recent planar bound of Aronov and Sharir [3]. Our analysis extends to yield the same bound (a) on the number of incidences between m points and n circles in any dimension d≥ 3, and (b) on the number of incidences between m points and n arbitrary convex plane curves in $\reals^d$, for any d≥ 3, provided that no two curves are coplanar. Our results improve the upper bound on the number of congruent copies of a fixed tetrahedron in a set of n points in 4-space, and were already used to obtain a lower bound for the number of distinct distances in a set of n points in 3-space.