Алгоритм нахождения максимальной сферы в зазоре между множеством сфер

Question

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

В настоящее время мой подход - это метод "толкания и выпуклости", при котором я выбираю точку P в пустоте вблизи центра всех сфер, и я нахожу самый большой шар с центром в P.Затем я позволяю центру шара пройтись небольшими шагами от P до новой позиции P 'и проверяю, пересекается ли шар в точке P' со старым радиусом с другими сферами, если пересечения не существует, сфера растет, пока не достигнет одной сферы, иначецентр снова ходит и повторяется.

Этот подход довольно трудоемкий, и мне интересно, есть ли лучший способ решения проблемы.Я искал в Интернете, и единственные уместные обсуждения касаются нахождения максимального вписанного круга / сферы между точками / многоугольником / многогранником.

Answer 1

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

Для 4 сфер есть только одна сфера, которая касается всех из них.(положение и радиус - 4 неизвестных, определяемые 4 уравнениями расстояния до заданных сфер)

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

Эта идея разбивает вашу проблему на конечное число возможностей.Простой алгоритм берет O (n ^ 5), что все еще долго, хотя, если у вас много сфер.Вы можете использовать трехмерную диаграмму Вороного, чтобы значительно ускорить это, как подсказывает @YvesDaoust.