title: How to compute the smallest bounding sphere enclosing other bounding spheres
body: <p>I'm looking for an algorithm which someone has access to that will compute the smallest bounding sphere that encloses a set of other bounding spheres. I have thought about this for a while and have come up with some initial solutions, but I don't believe these are necessarily the most accurate or the least computationally expensive (fastest).</p>
  
  <h2>First Thought</h2>
  
  <p>My first solution is the simplest naive one, which is to average out the sphere centers to get the center point, and then compute the maximum distance from the calculated center to each sphere's center plus its radius, as the radius. So pseudo code goes like:</p>
  
  <pre><code>function containing_sphere_1(spheres)
    center = sum(spheres.center) / count(spheres)
    radius = max(distance(center, spheres.center) + radius)
    return Sphere(center, radius)
  end
  </code></pre>
  
  <p>However I get the feeling that it isn't that computationally cheap, nor is it quite accurate since the resulting sphere could be quite larger than it needs to be.</p>
  
  <h2>Second Thought</h2>
  
  <p>My second thought is to use an iterative algorithm to compute the minimal bounding sphere. It is computed by successively testing another sphere, if the tested sphere is inside the bounds, then nothing is done, otherwise a new bounding sphere is computed from the two spheres available. The new bounding sphere has a center that is half way between the vector between the two centers if it was extended to the spheres surfaces, and the radius is the half the length of that line (from the new center to either sphere's surface).</p>
  
  <pre><code>function containing_sphere_2(spheres)
    bounds = first(spheres)
    for each sphere in spheres
      if bounds does not contain sphere
        line = vector(bounds.center, sphere.center)
        extend(line, bounds.radius)
        extend(line, sphere.radius)
        center = midpoint(line)
        radius = length(line) / 2
        bounds = Sphere(center, radius)
      end
    end
    return bounds
  end
  </code></pre>
  
  <p>Initially I thought that this would be the way to go, since it is iterative and seems fairly logically consistent, however after doing some reading, most notably the article "Smallest enclosing disks (balls and ellipsoids)" by Emo Welzl I'm not not so sure.</p>
  
  <h2>Welzl's Algorithm</h2>
  
  <p>As I understand it the basis of this algorithm is that the minimum bounding sphere over a set of points in 3 dimensions can be determined by at most 4 points (which are on the surface of the enclosing sphere). So the algorithm takes an iterative approach by selecting 4 points, and then testing other points to see if they're inside or not, if they aren't a new bounding sphere is constructed featuring the new point. </p>
  
  <p>Now the algorithm deals strictly with points, but I think it can be applied to deal with spheres, the main complication being accounding for the radius when constructing the enclosing sphere.</p>
  
  <h2>Back to the Question</h2>
  
  <p>So what is the 'best', as in least computationally expensive, algorithm that creates a minimal bounding sphere for a set of given spheres?</p>
  
  <p>Is one of these I have described here the answer? Some pseudo code or the algorithm would be great.</p>