given N circles,how many pairs intersect

[usfish]

Hi all,

So on plane, given N circles, with radius and coordinates of centers known, is there any good way to figure out how many pairs of circles intersect? I mean an algorithm with <n^2 complexity.

a pair of circles intersect when the distance between their centers is smaller than the sum of their radii.

Thanks!!

[maxdiver]

It looks like very hard problem.
Even the following problem, which is a simplification of this one, is very hard: there is a set S of N points on plane, and the query is some circle; we should return number of points from S inside the circle. This problem (which is mentioned in Shamos, Preparata) can be solved using Voronoi diagrams in O(N^3) preprocessing and O(log N log log N) per query. Using method of "filtering search" (Chazelle "Filtering search: A new approach to query answering") it can be solved in O (N (log N log log N)^2) for preprocessing and O (log N) per query.
And it looks like your problem is even harder than this one...

[hwwong]

It looks like very hard problem.
Even the following problem, which is a simplification of this one, is very hard: there is a set S of N points on plane, and the query is some circle; we should return number of points from S inside the circle. This problem (which is mentioned in Shamos, Preparata) can be solved using Voronoi diagrams in O(N^3) preprocessing and O(log N log log N) per query. Using method of "filtering search" (Chazelle "Filtering search: A new approach to query answering") it can be solved in O (N (log N log log N)^2) for preprocessing and O (log N) per query.
And it looks like your problem is even harder than this one...

?_? Aren't there at most n(n-1)/2 pairs? So O(n^2) solution is to exhaust every pair of circles...