COUNTING CIRCULAR-ARC INTERSECTIONS

In this paper efficient algorithms for counting intersections in a col lection of circles or circular arcs are presented. An algorithm for co unting intersections in a collection of n circles is presented whose r unning time is O(n3/2+epsilon), for any epsilon > 0 is presented. Usin g this algorithm as a subroutine, it is shown that the intersections i n a set of n circular arcs can also be counted in time O(n3/2+epsilon) . If all arcs have the same radius, the running time can be improved t o O(n4/3+epsilon), for any epsilon > 0.