Как вычислить наименьшую ограничивающую сферу, включающую другие ограничивающие сферы

Я ищу алгоритм, к которому у кого-то есть доступ, который вычислит наименьшую ограничивающую сферу, которая включает в себя набор других ограничивающих сфер. Я думал об этом некоторое время и придумал некоторые начальные решения, но я не считаю, что они обязательно самые точные или наименее затратные (самые быстрые) с точки зрения вычислений.

Первая мысль

Мое первое решение - простейшее наивное, которое заключается в том, чтобы усреднить центры сфер, чтобы получить центральную точку, а затем вычислить максимальное расстояние от вычисленного центра до центра каждой сферы плюс ее радиус, как радиус. Итак, псевдокод выглядит примерно так:

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

Однако у меня такое чувство, что он не так дешев с вычислительной точки зрения и не совсем точен, поскольку полученная сфера может быть намного больше, чем должна быть.

Вторая мысль

Моя вторая мысль - использовать итерационный алгоритм для вычисления минимальной ограничивающей сферы. Он вычисляется путем последовательного тестирования другой сферы, если проверяемая сфера находится внутри границ, то ничего не делается, в противном случае новая ограничивающая сфера вычисляется из двух доступных сфер.Новая ограничивающая сфера имеет центр, который находится на полпути между вектором между двумя центрами, если он был продлен до поверхностей сфер, а радиус равен половине длины этой линии (от нового центра до любой поверхности сферы).

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

Сначала я подумал, что это будет правильный путь, поскольку он является итеративным и кажется довольно логически последовательным, однако после некоторого прочтения, в первую очередь, статьи Эмо Вельцля I «Наименьшие охватывающие диски (шары и эллипсоиды)» м не очень уверен.

Алгоритм Вельцля

Насколько я понимаю, в основе этого алгоритма лежит то, что минимальная ограничивающая сфера над набором точек в трех измерениях может быть определена не более чем по 4 точкам (которые находятся на поверхности охватывающей сферы) . Таким образом, алгоритм использует итеративный подход, выбирая 4 точки, а затем проверяя другие точки, чтобы увидеть, находятся ли они внутри или нет, если это не новая ограничивающая сфера, построенная с новой точкой.

Теперь алгоритм имеет дело только с точками, но я думаю, что он может быть применен к сферам, основная сложность заключается в вычислении радиуса при построении охватывающей сферы.

Вернуться к вопросу

Итак, какой же «лучший», по меньшей мере, затратный с точки зрения вычислений алгоритм, который создает минимальную ограничивающую сферу для набора заданных сфер?

Является ли один из описанных мною здесь алгоритмом отвечать? Какой-нибудь псевдокод или алгоритм были бы замечательными.