## given N circles,how many pairs intersect

Moderator: Board moderators

usfish
New poster
Posts: 1
Joined: Sat Oct 18, 2008 2:59 am

### given N circles,how many pairs intersect

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
Learning poster
Posts: 51
Joined: Tue Sep 04, 2007 2:12 pm
Location: Russia, Saratov
Contact:

### Re: given N circles,how many pairs intersect

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
New poster
Posts: 4
Joined: Sun Dec 07, 2008 3:12 pm

### Re: given N circles,how many pairs intersect

maxdiver wrote: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...