3
$\begingroup$

I have a set of circles on a plane, each defined by their X, Y and R parameters. I need to find the smallest enclosing circle over all of them. Essentially, this is a variation of this question, except my circles can have different radii. What would be a fast (linear time) algorithm of doing that?

I'm posting it here instead of StackOverflow/programmers.se because I think this is a predominantly math problem, rather than programming. Please correct me if I'm wrong.

My math is OK-ish, but I'm struggling to come up with a good solution. The best I've come up with is to replace each circle with 8 points, and then calculate the SEC for those with the help of Welzl's algorithm. It will not be exact, but should be an acceptable approximation for my purposes. However I wonder if there is a better and more precise algorithm?

$\endgroup$
3
$\begingroup$

Real solution:

B. Gärter from ETH zurich has come up with this C++ package embodying the algorithm to solve the problem. Even in higher dimensions. https://people.inf.ethz.ch/gaertner/subdir/software/miniball.html

more info here: https://www.inf.ethz.ch/personal/emo/DoctThesisFiles/fischer05.pdf

I leave my previous answers below so people can see how primitive they are.

Approximation involving center of mass of the points:

Let $c(x_i,y_i,r_i)$ define a circle with position $(x_i,y_i)$ and radius $r_i$

Let $(x_c,y_c) = { (\sum_{i=1}^{n}x_i/n \:,\sum_{i=1}^{n}y_i/n)} \:\:\:\:\:$ be the center of of mass of the $n$ circle positions.

Next our concern is finding the smallest radius $r_c$ that encloses the circles from the center of mass.

This is done by finding the maximum value of the distance from the center $(x_c,y_c)$ to the circle center positions $(x_i,y_i)$ plus their radius $r_i$:

$r_c = max (\sqrt{(x_c - x_j,y_c-y_j) \cdot (x_c - x_j,y_c -y_j)}+r_j)$

We now have a circle $C(x_c,y_c,r_c)$ enclosing the other circles. This is not the optimal circle but the algorithm to find it is linearly bounded, $o(n)$.

Approximation involving the smallest enclosing rectangle for the circles

This is a basic approach that finds the enclosing rectangle defined by its boundaries. We obtain $Rect(x_{min}, x_{max}, y_{min}, y_{max})$ that defines the boundaries of an axis oriented rectangle. Where:

$x_{min} = min( \:x_j - r_j)$

$x_{max} = max( \:x_j + r_j)$

$y_{min} = min( \:y_j - r_j)$

$y_{max} = max( \:y_j + r_j)$

Now the center of our enclosing circle is $(x_c,y_c ) = ((x_{min}+ x_{max})/2\:, (y_{min} + y_{max})/2)$

We obtain the radius as before:

$r_c = max (\sqrt{(x_c - x_j,y_c-y_j) \cdot (x_c - x_j,y_c -y_j)}+r_j)$

We now have a circle $C(x_c,y_c,r_c)$ enclosing the other circles. This is not the optimal circle but the algorithm to find it is linearly bounded, $o(n)$. Its a start I hope someone posts an exact solution. Its an interesting problem.

$\endgroup$
  • $\begingroup$ This is the first idea that came to my mind, but I quickly discarded it. Consider the scenario where there are 101 circles, all with the same radius. 100 of them are closely clustered, while the last one is a fair deal further from the rest. The center of the mass will be somewhere inside the crowd, while the outlying circle will make the radius way, way bigger than necessary. $\endgroup$ – Vilx- Sep 20 '16 at 14:58
  • $\begingroup$ @Vilx- Why are you trying to get the solution to this problem? What is the domain You are bringing it from? It looks nontrivial. A more suitable solution could be arrived at by making the circle smaller and sliding it in the direction of the max position until you hit a second circle. $\endgroup$ – MNKY Sep 20 '16 at 21:22
  • $\begingroup$ @Vilx- another possible approximate solution is to find the smallest enclosing rectangle for our circles and use its center as the center of the enclosing circle. It's basic but it's cheap computationally. $\endgroup$ – MNKY Sep 21 '16 at 0:22
  • $\begingroup$ @igael : I was not thinking of rotating rectangles, just axis oriented ones, I edited the sol to explain what I mean. $\endgroup$ – MNKY Sep 21 '16 at 5:27
  • $\begingroup$ I need this for a force-directed graph layout algorithm, and the problem there is pretty much exactly this. I need to group a bunches of nodes (circular) and calculate forces between these groups, taking the size (visual, not count or weight) of the group into account, so that the groups don't overlap. $\endgroup$ – Vilx- Sep 21 '16 at 7:10

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.