Counting Circular Arc Intersections
Pankaj K. Agarwal, Marco Pellegrini, Micha Sharir · SIAM Journal on Computing · 1993
In this paper efficient algorithms for counting intersections in a collection of circles or circular arcs are presented. An algorithm for counting intersections in a collection of n circles is presented whose running time is $O(n^{{3 / {2 + \epsilon }}} )$, for any $\epsilon > 0$ is presented. Using this algorithm as a subroutine, it is shown that the intersections in a set of n circular arcs can also be counted in time $O(n^{{3 / {2 + \epsilon }}} )$. If all arcs have the same radius, the running time can be improved to $O(n^{{4 / {3 + \epsilon }}} )$, for any $\epsilon > 0$.