3

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?

Community
  • 1
Vilx-
  • 305
  • Hint: The smallest enclosing circle of a set of points can be found in time O(N Log(N)) using the farthest-point Voronoi diagram. I wouldn't be surprised that this can be generalized to circles of different radii using a weighted Voronoi. –  Sep 20 '16 at 07:06
  • @Vilx- This https://www.inf.ethz.ch/personal/emo/DoctThesisFiles/fischer05.pdf is a paper that might help you. – MNKY Sep 23 '16 at 13:19
  • @Vilx- This is a package of an algorithm that solves your problem: https://people.inf.ethz.ch/gaertner/subdir/software/miniball.html – MNKY Sep 23 '16 at 14:29

1 Answers1

3

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.

MNKY
  • 431
  • 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. – Vilx- Sep 20 '16 at 14:58
  • @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. – MNKY Sep 20 '16 at 21:22
  • @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. – MNKY Sep 21 '16 at 00:22
  • @igael : I was not thinking of rotating rectangles, just axis oriented ones, I edited the sol to explain what I mean. – MNKY Sep 21 '16 at 05:27
  • 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. – Vilx- Sep 21 '16 at 07:10
  • @igael : cool script you made there. – MNKY Sep 21 '16 at 07:13
  • @MNKY : finally, I prefer your answer ... :) –  Sep 21 '16 at 14:14
  • @igael : ahh thanks mate . Where did your script go? I had some fun with it yesterday. What i suspect is that the optimal circle will be in contact with 2 circles or more when the contacts bisect the circle and with 3 circles or more when they do not. – MNKY Sep 22 '16 at 04:17
  • @MNKY: the pp found that it didn't fit his hope ... frustrating after some hours of tuning ! I published it again ; url in the browser history... Sorry and thank you –  Sep 22 '16 at 13:40
  • Ahh, great! That's exactly the paper I was looking for! Nice :) Although it does look like some dense reading. Will see if I can break through it. :) – Vilx- Sep 23 '16 at 17:06