How to find and print intersections of n given circles in O(n*log(n)) time?

Question

I'm looking for an O(n*logn) algorithm to find and print the intersections of n given circles. Each circle is specified by its center and radius.

An O(n²) algorithm consists in checking if the distance between the centers is less than or equal to the sum of the radii (of the two circles being compared). However, I'm looking for a faster one!

A similar problem is intersection of line segments. I think even my problem can be solved using line sweep algorithm, but I am unable to figure out how to modify the event queue in-case of circles.

Please, take also care of the following corner case. The black points indicate the event points (as per User Sneftel's solution below the intersection of circles marked by arrows won't be printed)

Answer 1

The line sweep algorithm will simply add circles to a list when you encounter their left extrema (that is, (x-r, y)), and removed from the list when you encounter their right extrema. Right before you add a circle to the list, check it against the circles already in the list. So your event queue is basically the left and right extrema of all circles, sorted by x. (Note that you know all the events ahead of time, so it's not really a "queue" in the normal sense.)

This is also known as "sweep and prune".

Answer 2

This is the correct solution I found based on a modification of User Sneftel's algorithm that wasn't working for all cases.

Fig 1 : Represent each circle by a bounded box.
Now to use the sweep line method, moving the sweep line parallel to y-axis we need TWO line segments to represent each circle's y-range as shown in figure 2.

Having done that the problem reduces to the following :

Here 2 line segments represent one circle.
Sweep line status can be maintained as any balanced dynamic data structure like AVL tree, Skip Lists, Red Black Trees having insertion/Update/Deletion/Retrieval time at-most O(logn).
The comparison function in this case will check if the two circles corresponding to the adjacent line segments intersect or not(In place of checking for line segments to intersect as in the original line sweep method for finding out line segment intersections). This can be done in O(1) time as constant amount of operations are required.
Number of Event Points : 4n (for n circles => 2n line segments => 4n end points)
Complexity = O(4nlog(4n)) = O(nlogn)