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!!

[pm_kirkham]

R-tree or other efficient rectangular spatial index using the bounding box of the circle, followed by a test whether the circles really do intersect.