Comment faire pour calculer le plus petit de délimitation de la sphère englobante autres délimitation des sphères

Je suis à la recherche d'un algorithme de quelqu'un qui a accès à qui permettra de calculer le plus petit de délimitation de la sphère qui entoure un ensemble de autres de délimitation des sphères. J'ai pensé à ce sujet pendant un certain temps et ont trouvé quelques solutions, mais je ne crois pas que ce sont nécessairement les plus exactes ou le moins gourmand en ressources (le plus rapide).

Première Pensée

Ma première solution est la plus simple, naïve, qui est de faire la moyenne de la sphère centres pour obtenir le point central, puis calculer la distance maximale de la valeur calculée centre de chaque sphère de centre et de son rayon, le rayon. Donc le pseudo-code comme:

function containing_sphere_1(spheres)
  center = sum(spheres.center) /count(spheres)
  radius = max(distance(center, spheres.center) + radius)
  return Sphere(center, radius)
end

Mais j'ai le sentiment que ce n'est pas que le calcul à bas prix, ni tout à fait exacte, puisque la sphère pourrait être bien plus grand qu'il doit être.

Deuxième Pensée

Ma deuxième pensée est d'utiliser un algorithme itératif pour calculer le minimum de délimitation de la sphère. Il est calculé par, successivement, de tester un autre sphère, si l'testé sphère est à l'intérieur des limites, alors rien n'est fait, sinon une nouvelle délimitation de la sphère est calculée à partir des deux sphères disponibles. La nouvelle délimitation de la sphère a un centre qui est à mi-chemin entre le vecteur entre les deux centres s'il a été étendu à toutes les sphères de surfaces, et le rayon est la moitié de la longueur de la ligne (à partir de la nouveau centre, soit de surface de la sphère).

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

J'ai d'abord pensé que ce serait le chemin à parcourir, car il est itératif et semble assez logiquement cohérente, cependant après avoir fait un peu de lecture, et plus particulièrement l'article "Petit joignant les disques (balles et des ellipsoïdes)" par Emo Welzl je ne suis pas si sûr.

Welzl l'Algorithme de

Si je comprends bien la base de cet algorithme est que le minimum de délimitation de la sphère sur un ensemble de points dans les 3 dimensions peut être déterminée par au plus 4 points (qui sont sur la surface de la sphère englobante). Donc, l'algorithme prend une approche itérative en sélectionnant 4 points, puis de le tester d'autres points à voir si ils sont à l'intérieur ou pas, si ils ne sont pas d'une nouvelle délimitation de la sphère est construit, mettant en vedette le nouveau point.

Maintenant l'algorithme traite strictement avec les points, mais je pense qu'il peut être appliqué à traiter avec des sphères, la principale complication étant accounding pour le rayon lors de la construction de la sphère englobante.

Revenir à la Question

Alors, quelle est la "meilleure", comme dans la moins coûteuse en termes de calcul, l'algorithme qui crée un minimum de délimitation de la sphère pour un ensemble de sphères?

Est l'un de ces je l'ai décrit ici la réponse? Pseudo-code de l'algorithme serait génial.