Circle intersections algorithm with $O((n+s)\log(n))$ complexity

Question

I have found a few different posts about finding the intersections of circles in $O((n+s)\log(n))$ time with $n$ the amount of circles and $s$ the amount of intersections. The problem is that none of the answers are giving a clear and steady answer.

I found this answer that looked very interesting, but I still have my doubts about it. Snetfel explained that we can use a sweep-line algorithm. Here is a brief summary:

We make a priority queue containing all $x$ points of left $(x-r)$ and right $ (x+r)$ extremas of the circles. We then use a binary tree to respresent the sweep-line status.

• Whenever we encounter a left extrema of a circle, we add it to the status and check for intersections with every other active circle in the status.
• Whenever we encounter a right extrema of a circle, we remove it from the status.

Here you can find a video I made so you can have a better understanding. But does this method do the job in $O((n+s)\log(n))$ time as we are still checking each added circle to all other circles in the status?

I tried another method which failed miserably.

My failed attempt

What I tried is the following.

We again make a priority queue containing all $x$ points of left $(x-r)$ and right $(x+r)$ extremas of the circles.

Start of circle $c$

1. Insert the circle with its center y value into a binary tree. (so you sort the binary tree by its $y$ value)
2. Check for intersection between circle $c$ and its predecessor.
3. Check for intersection between circle $c$ and its successor.

End of circle $c$

1. Check for intersection between the predecessor and successor of circle $c$.
2. Remove the circle from the binary tree.

But I noticed that this doesn't find all intersection points on a circle. For example, a circle with a high $y$ value and a huge radius, will not be compared to a circle with a very low $y$ value, eventhough they have an intersection.

Here you can find a sketch of my idea.

I found on different sources online that you can divide the circle in two semicircles. But by what value do you key your tree? How do you sort it so you can find the right neighbours?

Answer 1

But does this method do the job in $O((n+s)\log(n))$ time as we are still checking each added circle to all other circles in the status?

This is not true. We only need to check for intersection with the newly added circle’s predecessor and successor – that’s why we need the (balanced) binary search tree (e.g., an AVL tree), as it can perform this operation in $O(\log n)$ time.

When performing the line sweep, we have three types of events that we process with the priority queue:

Start of circle $c$

1. Insert $c$ into the binary search tree
2. Check for intersection between $c$ and its successor
3. Check for intersection between $c$ and its predecessor

End of circle $c$

1. Check for intersection between the predecessor of $c$ and the successor of $c$
2. Remove $c$ from the binary search tree

Intersection between $c_1$ and $c_2$

1. Note the intersection
2. Swap $c_1$ and $c_2$ within the binary search tree
3. Check for intersection between $c_1$ and its new neighbor
4. Check for intersection between $c_2$ and its new neighbor

Because there are $O(n + s)$ events and both the operations on the priority queue and the tree take $O(\log n)$ time, the final complexity is $O((n + s) \log n)$.

By the way, a tricky point is that we don’t have a well-defined ordering of the circles along the sweep line. However, we can rectify this by using the top and bottom semicircles instead.

EDIT: To clarify, when you insert a new (semi)circle into the binary search tree, you use its current $y$-coordinate and compare that to the current $y$-coordinates of the other (semi)circles to determine where on tree the new one should go. By “current” I mean relative to the $x$-coordinate of the sweep line, e.g., $$ y(x) = y_0 \pm \sqrt{r^2 - (x - x_0)^2}\text. $$