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!!
given N circles,how many pairs intersect
Moderator: Board moderators

 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...
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...
Re: given N circles,how many pairs intersect
?_? Aren't there at most n(n1)/2 pairs? So O(n^2) solution is to exhaust every pair of circles...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...