<p>A modified Bentley-Ottmann sweep algorithm (<a href="http://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm" rel="nofollow">here</a>, for example) will find all line segment intersections in $O((n+k)\log n + k)$ time, where $k$ is the number of intersections.  It's fairly straightforward to extend the algorithm to handle circles. A good walkthrough is <a href="http://www.cs.mcgill.ca/~jsatta/pr507/algo.html" rel="nofollow" title="here">here</a> under "finding intersections".</p>

<p>$k$ can be $\Omega(n^2)$ in theory (in which case pairwise checking is faster), but it seems difficult to avoid the $k$ term, and in any case you seem to say $k$ will be small in your question.</p>

<p>Granted, this recomputes the intersections from scratch each time you run the algorithm, which may be inefficient for your purposes.  You may be able to get around this a bit by maintaining the list of circles sorted by $x$ coordinate, and modifying this list online as the circles move.  This won't help your asymptotic running time, but it avoids sorting each circle every time.  If the circles stay relatively sparse (few cross the same vertical line), the binary search tree on the $y$-coordinates will be cheap to maintain.</p>

<p>The other issue is that knowing two circles intersect already does not improve the running time at all.  Once two circles attach to each other, you will calculate their intersection every single time, which is a waste.</p>

CC BY-SA 3.0
2013-04-25T18:13:58.263Z
2013-04-25T18:22:16.970Z
2013-04-25T18:22:16.970Z
SamM
<p>You could use something like a PKTree (or other spatial index), even though they do not take into account the radius of the circle.  How?  By using the range search algorithms over these data structures.  Put the centres of the circles into the data structure, then do a range search for a circle (or even bounding box, if that's easier on the structure you choose) of a radius twice the radius of your largest circle.  Then do a simple search within the results to find "actual" intersections.</p>

<p>This only works well if you don't have one circle that is significantly larger than most others.</p>

<p>Your worst case will be within <code>n * (&lt;range search of datastructure&gt; + n)</code>, which is terrible, but that second n will in practise (that is, in the non-worst-case) not be n and will be small (if you choose an appropriate data structure).</p>

CC BY-SA 3.0
2013-03-25T22:02:47.170Z
2013-03-25T22:02:47.170Z
singpolyma
<p>I have a collection of N circles in the plane with various position and radius. Circles move around according to one force and become bound to each other once they overlap. 
I need a fast way to determine if a circle is overlapped/overlaps another, to determine the circle's equations of motion during a time step. 
Once circles have overlapped, they are bound, so it's easy to remember that relationship. 
The problem is to evaluate when circles overlap for the first time. 
Think of cheerios floating on milk. </p>

<p>Obviously I have thought of using a KDTree or a Delaunay Triangulation, but these only take into account the circle centers, not their radius, so the closest circle in a DT Trianle isn't necessarily overlapping, while another might be.</p>

<p>I've read somewhere that a MWVD might work, but I don't understand how that would work. 
D Eppstein has a couple of papers out on Mobius Transformations, and that too is over my head, but it looks like it's related. 
Can anyone point me in the right direction ?</p>

<p>Thanks.</p>

CC BY-SA 3.0
2013-03-19T17:32:35.580Z
Can you tell us more about what you want to do with these circles?  How dense the intersection graph is, and whether or not it is dynamic?  If the graph is dense and dynamic, you may as well just test your $N$ circles when you need the list of circles intersecting a given circle, as you can do this in constant time per circle pair anyway.
Andrew D. King
CC BY-SA 3.0
2013-03-20T03:19:06.813Z
Sure. The circles move around according to one gravity-like 'force' as long as they don't overlap. Once they overlap, a second rigid spring-like relationship takes over. Once they have overlapped, I can keep track of these relationships, so I don't need to re-discover those overlaps, but I want to discover the new ones. Because of the spring-like behavior, the graph is not quite dynamic, not sparse, but also never a complete graph.
jdbertron
CC BY-SA 3.0
2013-03-20T17:04:21.080Z
Why never a complete graph, if they are attracted by a gravity-like force?  And do you mean that once they touch, they remain touching, as might balloons with static electricity?  It seems to me that either you should go for a $k$-d tree or resign yourself to a quadratic method, and have the "force" reflect whether or not the distance between the centres is greater than the sum of the two radii.
Andrew D. King
CC BY-SA 3.0
2013-03-21T00:30:19.597Z
Because in a complete graph the nodes are all connected, but in this case, the repulsion limits the possible overlaps, and therefore the number of connections. I think it is in fact a planar graph but I wouldn't venture to prove it.
jdbertron
CC BY-SA 3.0
2013-03-22T03:46:16.257Z
Please modify the original problem statement to take the motion of the circles into account.  Also: What does "visited" mean?
Jeffε
CC BY-SA 3.0
2013-03-24T17:43:31.190Z
Circles become joined once they have overlapped, and the relationship between their motions become 'sticky'. Otherwise, circles that have never overlapped move around according to a gravity-like force that isn't O(n^2). Because of the stickyness, I can keep a short list of the neighbours. Think of cheerios floating on a cup of milk. They are attracted to each other but once they touch they're bound to each other.
jdbertron
<ds.algorithms><ds.data-structures>
Efficient algorithm to find overlapping circles of various sizes
jdbertron
# Efficient algorithm to find overlapping circles of various sizes

(Asked by: username_0 on 2013-03-19)

I have a collection of N circles in the plane with various position and radius. Circles move around according to one force and become bound to each other once they overlap.
I need a fast way to determine if a circle is overlapped/overlaps another, to determine the circle's equations of motion during a time step.
Once circles have overlapped, they are bound, so it's easy to remember that relationship.
The problem is to evaluate when circles overlap for the first time.
Think of cheerios floating on milk.

Obviously I have thought of using a KDTree or a Delaunay Triangulation, but these only take into account the circle centers, not their radius, so the closest circle in a DT Trianle isn't necessarily overlapping, while another might be.

I've read somewhere that a MWVD might work, but I don't understand how that would work.
D Eppstein has a couple of papers out on Mobius Transformations, and that too is over my head, but it looks like it's related.
Can anyone point me in the right direction ?

Thanks.

**Tags:** ds.algorithms, ds.data-structures

> **Comments:**
> **username_1**: Can you tell us more about what you want to do with these circles?  How dense the intersection graph is, and whether or not it is dynamic?  If the graph is dense and dynamic, you may as well just test your $N$ circles when you need the list of circles intersecting a given circle, as you can do this in constant time per circle pair anyway.  
> **username_0**: Sure. The circles move around according to one gravity-like 'force' as long as they don't overlap. Once they overlap, a second rigid spring-like relationship takes over. Once they have overlapped, I can keep track of these relationships, so I don't need to re-discover those overlaps, but I want to discover the new ones. Because of the spring-like behavior, the graph is not quite dynamic, not sparse, but also never a complete graph.  
> **username_1**: Why never a complete graph, if they are attracted by a gravity-like force?  And do you mean that once they touch, they remain touching, as might balloons with static electricity?  It seems to me that either you should go for a $k$-d tree or resign yourself to a quadratic method, and have the "force" reflect whether or not the distance between the centres is greater than the sum of the two radii.  
> **username_0**: Because in a complete graph the nodes are all connected, but in this case, the repulsion limits the possible overlaps, and therefore the number of connections. I think it is in fact a planar graph but I wouldn't venture to prove it.  
> **username_2**: Please modify the original problem statement to take the motion of the circles into account.  Also: What does "visited" mean?  
> **username_0**: Circles become joined once they have overlapped, and the relationship between their motions become 'sticky'. Otherwise, circles that have never overlapped move around according to a gravity-like force that isn't O(n^2). Because of the stickyness, I can keep a short list of the neighbours. Think of cheerios floating on a cup of milk. They are attracted to each other but once they touch they're bound to each other.  

---

## 2 answers

### Answer by username_3 on 2013-04-25. Score: 4

A modified Bentley-Ottmann sweep algorithm ([here](http://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm), for example) will find all line segment intersections in $O((n+k)\log n + k)$ time, where $k$ is the number of intersections. It's fairly straightforward to extend the algorithm to handle circles. A good walkthrough is [here](http://www.cs.mcgill.ca/~jsatta/pr507/algo.html "here") under "finding intersections".

$k$ can be $\Omega(n^2)$ in theory (in which case pairwise checking is faster), but it seems difficult to avoid the $k$ term, and in any case you seem to say $k$ will be small in your question.

Granted, this recomputes the intersections from scratch each time you run the algorithm, which may be inefficient for your purposes. You may be able to get around this a bit by maintaining the list of circles sorted by $x$ coordinate, and modifying this list online as the circles move. This won't help your asymptotic running time, but it avoids sorting each circle every time. If the circles stay relatively sparse (few cross the same vertical line), the binary search tree on the $y$-coordinates will be cheap to maintain.

The other issue is that knowing two circles intersect already does not improve the running time at all. Once two circles attach to each other, you will calculate their intersection every single time, which is a waste.


---

### Answer by username_4 on 2013-03-25. Score: 1

You could use something like a PKTree (or other spatial index), even though they do not take into account the radius of the circle. How? By using the range search algorithms over these data structures. Put the centres of the circles into the data structure, then do a range search for a circle (or even bounding box, if that's easier on the structure you choose) of a radius twice the radius of your largest circle. Then do a simple search within the results to find "actual" intersections.

This only works well if you don't have one circle that is significantly larger than most others.

Your worst case will be within `n * ( + n)`, which is terrible, but that second n will in practise (that is, in the non-worst-case) not be n and will be small (if you choose an appropriate data structure).


---

