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?
Best Answer
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.