Circle Intersection with Sweep Line Algorithm

Question

Unfortunately I am still not so strong in understanding Sweep Line Algorithm. All papers and textbooks on the topic are already read, however understanding is still far away. Just in order to make it clearer I try to solve as many exercises as I can. But, really interesting and important tasks are still a challenge for me.

The following exercise I found in lecture notes of Line Segment Intersection by omnipotent Jeff Erickson.

Exercise 2. Describe and analyze a sweepline algorithm to determine, given $n$ circles in the plane, whether any two intersect, in $O(n \log n)$ time. Each circle is specified by its center and its radius, so the input consists of three arrays $X[1.. n], Y [1.. n]$, and $R[1.. n]$. Be careful to correctly implement the low-level primitives.

Let's try to make a complex thing easier. What do we know about intersection of circles? What analogue can be found with intersection of lines. Two lines might intersect if they adjacent, which property two circle should have in order to intersect? Let $d$ be the distance between the center of the circles, $r_{0}$ and $r_{1}$ centers of the circles. Consider few cases:

• Case 1: If $d > r_{0} + r_{1}$ then there are no solutions, the circles are separate.

• Case 2: If $d < |r_{0} - r_{1}|$ then there are no solutions because one circle is contained within the other.

• Case 3: If $d = 0$ and $r_{0} = r_{1}$ then the circles are coincident and there are an infinite number of solutions.

So, it looks like conditions of intersection are ready, of course it may be wrong conditions. Please correct if it's so.

Algorithm. Now we need to find something in common between two intersecting circles. With analogue to line intersection, we need to have insert condition and delete condition to event queue. Let's say event point are x coordinate of the first and the last points which vertical sweep line touches. On the first point we insert circle to status and check for intersection (3 cases for checking are mentioned above) with nearest circles, on the last point we delete circle from status.

It looks like is enough for sweep line algorithm. If there is something wrong, or may be there is something what should be done different, feel free to share your thoughts with us.

Addendum:

I insert a circle when vertical sweep line touches the circle for the first time, and remove a circle from the status when sweep line touches it for the last time. The check for intersection should be done for the nearest previous circle. If we added a circle to status and there was already another circle which we added before and it was still there, therefore the pervious circle was not "closed", so there might be an intersection.

Answer 1

You're definitely on the right track. The big question is: when you insert a circle, which other circles do you check for intersection? How do you perform this check?

In the line segment intersection case, the line segments at any given x coordinate are totally ordered. (You can list them from lowest to highest Y coordinate). Thus, you can maintain the line segments in a binary search tree, and when you add a new segment, you only need to find out where it belongs in the binary search tree, and check its neighbors for intersection events.

In the circles case, its not immediately clear which circles to check. If your answer is "all of them" then your algorithm needs some work.

Can you figure out a way to represent the circles so that they are totally ordered, like the line segments are?

Try representing the circles as two half-circles. Each insert event is actually two events: insert top half, and insert bottom half.

Answer 2

I could think of this approach analogous to Bentley Ottmann sweep that runs in O((n+k)logn) time.

I could reduce the problem of circle intersection to line segment intersection. I will consider the vertical diameter parallel to Y-axis for each of the circles. The algorithm shall use a horizontal line that sweeps the plane from bottom to top.

Now we have Upper end point, lower end point for each of the circles. Also, we need to modify the Intersection predicate to say that two segments intersect if and only if the sweep line cuts through both the circles at a point.

Since the line intersection problem can be solved in O( (n+k) logn ) time, the same bound follows for circle intersection as well.

I am quite convinced that this would work but if you guys could point out any case that this will not handle in general, do let me know.