6

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(n2) 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)

Please take care of this in your solution

Improve this question
3
  • Are your circels sorted (e.g. by their center-x-coordinate)? Afaik they need to be sorted for line sweep to work efficiently (Nevermind, your edit makes this clear)
    – user1781290
    Nov 28, 2013 at 11:58
  • No they are not, but as an initialization step, they may be sorted easily in O(nlogn) not affecting my desired bound of O(nlogn).
    – Sahil Sareen
    Nov 28, 2013 at 12:00
  • You mean intersection points of circle lines, right? Intersections of circles I would understand as areas. I find the drawing confusing. What are event points? Is this part of the question, or part of the solution?
    – johannes_lalala
    Apr 17, 2020 at 8:10

2 Answers 2

Reset to default
4

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".

Improve this answer
9
  • Yeah, for the event queue I could use skip lists/ AVL trees / Red Black trees or any balanced DS for O(logn) time insert/delete!
    – Sahil Sareen
    Nov 28, 2013 at 12:10
  • Or a sorted array. As I say, you know all your events ahead of time. There's no insertion or deletion, just iteration.
    – Sneftel
    Nov 28, 2013 at 12:19
  • 2
    I would definitely need a dynamic DS for finding out in each iteration which two circles become adjacent(to check for intersections in the sweep line status) rite?
    – Sahil Sareen
    Nov 28, 2013 at 12:21
  • You could use it for the active set of circles, true, and that might improve performance for circles which were not uniformly distributed. As a first pass, I would personally keep the active set as an array and do brute-force scan on the active circles. Which way is faster depends on how sparse your area is.
    – Sneftel
    Nov 28, 2013 at 12:24
  • There will be only a single pass isn't it? I think a single pass is sufficient. We could start with the circle having least value of (xc-r) ie the leftmost event point. Add it to the sweep line status and update the sweep line status as the algorithm proceeds.
    – Sahil Sareen
    Nov 28, 2013 at 12:27
2

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

enter image description here

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.

enter image description here

Having done that the problem reduces to the following :

enter image description here

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)

Improve this answer
2
  • 1
    I don't see how your comparison function works. If the circles intersect, which is ranked higher? How would you construct the data structure with this function? See stackoverflow.com/q/23548473/6742968
    – obsolesced
    Oct 31, 2016 at 5:52
  • 1
    Why bother with the second line segment? You can just store the highest line segment and additionally include the diameter of the circle to know big it is.
    – smac89
    Feb 5, 2019 at 2:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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