I have a problem as follows:

  • We have a set of circles (we know the radius r and the center point c in Rd of each circle)
  • We need to find lists. Each list contains circles that overlap and connect each other.
  • For example, we have 6 circles in 2D as bellows. We need to find two lists. The first list contains red, yellow, orange, and magenta circles. The second list contains blue and green circles.

An obvious solution is to check overlap of each pair, then find connected components. However, the complexity is O(N2). My question is whether there is any better solution. example

  • $\begingroup$ If you want to find circles that overlap each other wouldn't you have four lists? $\endgroup$
    – nicoguaro
    Dec 19, 2017 at 13:29
  • $\begingroup$ I mean finding regions that do not overlap. Four circles (organ, yellow, magenta, red) create a region A. Two circles (green, blue) create another region B. The region A and B do not overlap each other. $\endgroup$
    – khanhndk
    Dec 20, 2017 at 10:57
  • $\begingroup$ What if the circles overlap in a tree-like manner with branches? $\endgroup$
    – André
    Dec 20, 2017 at 12:00
  • $\begingroup$ It somehow looks like the finding connected components in a graph (Wikipedia). A circle is a vertice. If two circles overlap each other, we have an edge connected between two corresponding vertices. But if we cast the problem to finding connected components, we need to check overlap for all pairs of circles to build a graph before doing the algorithm for finding connected components. $\endgroup$
    – khanhndk
    Dec 21, 2017 at 1:28

2 Answers 2


You don't need to check each pair of circles, so you can apply one of the neighour search algorithms. They restrict the distance calculations to the circles in the vicinity of each other by generating a list of potential neighbours based on a certain division of space.

I would suggest to use the kd-tree method, which is efficient for circles with variable radii and has linear complexity. However, if you have only a few circles, brute-force method is more efficient.


Allow me to introduce a linear time, $C\cdot O(N) + O(W\cdot H)$ algorithm where $C$ denotes the number of circles, plus some small coefficient, and $O(W\cdot H)$ is always constant. In this one, you will not need KD-trees, which make it $O(N\cdot log(N))$ anyways. This of course, comes at the expense of some additional space consumption - though KD-trees also do, and a very acceptable approximation in certain cases.

What one could do is to render the circles on a fixed spatial domain, such as an image, and find the connected components on that image. It is then possible to directly find the equivalences, from the components in the image. Here is a pseudo-code of the idea:

   $\mathbf{I}$ $\leftarrow$ $\text{empty image}$

   $\text{for all} (circle \in \mathbf{C}$) $\{$

      $\mathbf{I} \gets \text{render_circle}(\mathbf{I}$, $circle$)


   $\mathbf{CC} \gets \text{conn_comp}(\mathbf{I})$

   $\text{look-up the label of each } circle \in \mathbf{C} \text{ from }\mathbf{CC}$

If one likes to consider the nested circles as connected, then the rendering (e.g. using Bresenham or midpoint algorithm) should be made filled, otherwise, boundary drawing is sufficient and makes the algorithm far more efficient (image is never fully traversed).

Let's take the following configuration: enter image description here

The connected components, $\mathbf{CC}$, looks like: enter image description here

and the mapping array contains values such as: $[2 ,3, 1, 2, 1, 4]$.

Below, I provide a very dirty, but hopefully working solution in MATLAB. It can be implemented much more efficiently, but this one in general, demonstrates the concept.

close all;

% some experimental parameters 
n = 6; % # circles
width = 256;
height = 256;
maxRadius = 60;

% generate some random data 
cx = rand(n, 1)*width;
cy = rand(n, 1)*height;
r = 4+rand(n, 1)*maxRadius;

circIds = cell(width*height, 1); % image, where each pixel is a an array

% now render the circles to integer coordinates
figure, hold on;
for i=1:n
    h = viscircles([cx(i), cy(i)], r(i), 'Color', colors(i,:));

    list = double(midPointCircle(r(i), cx(i), cy(i)));
    li = double(list(:,2));
    lj = double(list(:,1));
    invalid = (li<=0 | li>height | lj<=0 | lj>width);
    ind = sub2ind(([height, width]), li, lj);
    for j=1:length(circIds(ind))
        circIds(ind(j)) = {[cell2mat(circIds(ind(j))) i]};
drawnow; hold off;

% compute the label image 
I = zeros(height, width);
Ilogical = (false(height, width));
for i=1:length(circIds)
    C = circIds{i};
    for j=1:length(C)
        [row, col] = ind2sub(([height, width]), i);
        I(row, col) = C(j);
        Ilogical(row, col) = 1;
figure, imagesc(I);

% find the connected components on the image
Ccomp = bwlabel(Ilogical,8); % O(WH)
figure, imagesc(Ccomp);

mapping = zeros(n, 1);
% now collect the equivalences
for i=1:length(circIds)
    C = circIds{i};
    for j=1:length(C)
        [row, col] = ind2sub(([height, width]), i);
        mapping(C(j)) = Ccomp(row, col);
        if (all(mapping))
    if (all(mapping))

% the final connected components
  • $\begingroup$ It works only on 2D, doesn't it? My problem requires dealing with high dimensional space. $\endgroup$
    – khanhndk
    Dec 25, 2017 at 5:44
  • $\begingroup$ Well, you mention 'circles' which are always 2D - any circle can always be mapped to a 2D plane. However, if you speak of objects in more dimensions the question should be phrased differently. In 3D one could render spheres on a grid, which would still work up to the discretization. Higher dimensions might require more care. $\endgroup$ Dec 30, 2017 at 19:41

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.