Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
1  
Have you read the chapter in cs.uu.nl/geobook "Computational Geometry, Algorithms and Applications"? What are you not understanding? –  Joe Apr 23 '12 at 19:09
    
@Joe, I read it, great book on Computational Geometry, the chapter was clear, but when I solve (or more often try to solve) exercises I come to conclusion that it's not easy to use the concept of sweep line algorithm. –  com Apr 23 '12 at 19:15
4  
+1 for "omnipotent Jeff Erickson" which I think should be his name from now on –  Suresh Apr 23 '12 at 20:24
3  
omnipotent [citation needed] –  JeffE Apr 23 '12 at 21:08
    
@com what do you mean by "nearest previous circle"? –  Joe Apr 24 '12 at 0:28
show 2 more comments

2 Answers

up vote 5 down vote accepted

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.

share|improve this answer
    
Unfortunately I don't get the idea of semicircles, maybe you consider semicircle as a minimal unit of circle which can be intersected (3 cases of intersection: intersection is on upper semicircle, or on lower, or on both of them). At the begging all circles are ordered by x coordinate of their left and right boundaries. So we should not consider x coordinated in status, because all circles already come in x coordinate order. Therefore it seems more logical to consider y coordinate of the center (of semicircle), or any combination of y and radii. Your opinion? –  com Apr 24 '12 at 4:49
    
@com You need center point and radius to determine whether two circles intersect, as you have done in your own intersection checks. Just the y coordinate and the radius alone don't fully specify the boundary of the circle. There seems to be something fundamental about sweep line algorithms which you are not understanding, but it's hard for me to tell what it is. –  Joe Apr 24 '12 at 19:38
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.