15
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ omnipotent [citation needed] $\endgroup$ – JeffE Apr 23 '12 at 21:08
  • $\begingroup$ @com what do you mean by "nearest previous circle"? $\endgroup$ – Joe Apr 24 '12 at 0:28
  • 1
    $\begingroup$ I assume that status maintains the circles currently intersecting the sweep line? Suppose you currently have 100 circles in status, and you process an insertion event and insert the 101st circle. How many circles do you compare to check for intersection? How do you pick which circles to compare? $\endgroup$ – Joe Apr 24 '12 at 19:42
  • $\begingroup$ @Joe, this is exactly what I need, like in classical sweep line algorithm, where "intersection of two lines implies adjacency of these two lines at some point", I need to find the similar analogue with circles. The simplest thing I come with is $y$ lowest coordinate and $y$ highest coordinate of the circle, if the circle intersect their projection of intervals from the lowest $y$ to highest $y$ should intersect to. So maybe now I am getting closer to your idea of semicircles. Above semicircles contains the highest $y$, and below contains the lowest $y$. $\endgroup$ – com Apr 25 '12 at 15:16
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – com Apr 24 '12 at 4:49
  • $\begingroup$ @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. $\endgroup$ – Joe Apr 24 '12 at 19:38
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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