Введение

Сфера, содержащая множество объектов
Плоская задача

В математике, для непустого множества объектов конечного размера в n-мерном пространстве, например, множества точек, ограничивающая сфера, внешняя сфера или внешний шар для этого множества – это n-мерный твердый шар, содержащий все эти объекты. Ограничивающая сфера, используемая в компьютерной графике и вычислительной геометрии, является особым типом ограничивающего объема. Существует несколько быстрых и простых алгоритмов построения ограничивающих сфер, имеющих высокую практическую ценность в приложениях компьютерной графики в реальном времени. В статистике и исследовании операций объекты обычно представляют собой точки, и, как правило, интересующая сфера является минимальной ограничивающей сферой, то есть сферой с минимальным радиусом среди всех ограничивающих сфер. Можно доказать, что такая сфера единственна: если их две, то рассматриваемые объекты лежат внутри их пересечения. Однако пересечение двух несовпадающих сфер одинакового радиуса содержится в сфере меньшего радиуса. Задача вычисления центра минимальной ограничивающей сферы также известна как "неутяжеленная задача о центре Евклида 1".

Кластеризация

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

Алгоритмы

Существуют точные и приближённые алгоритмы для решения задачи нахождения ограничивающей сферы.

Линейное программирование

Нимрод Мегиддо всесторонне изучал проблему 1-го центра и опубликовал о ней как минимум пять раз в 1980-х годах. В 1983 году он предложил алгоритм "отсечения и поиска", который находит оптимальную ограничивающую сферу и работает за линейное время, если размерность фиксирована как константа. При учёте размерности сложность времени выполнения составляет , что непрактично для задач с высокой размерностью. В 1991 году Эмо Велцль предложил гораздо более простой рандомизированный алгоритм, обобщив рандомизированный алгоритм линейного программирования Раймунда Зайделя. Ожидаемое время работы алгоритма Велцля равно , что снова сводится к для любой фиксированной размерности . В статье представлены экспериментальные результаты, демонстрирующие его применимость в пространствах большей размерности. Более поздний детерминированный алгоритм Тимоти Чана также работает за время , с меньшей (но всё ещё экспоненциальной) зависимостью от размерности. Библиотека алгоритмов вычислительной геометрии с открытым исходным кодом (CGAL) содержит реализацию алгоритма Велцля.

Приближение на основе основных наборов

Бадоиу и др. представили аппроксимацию для задачи о минимальной охватывающей сфере, где аппроксимация означает, что построенная сфера имеет радиус не более αr, где r – наименьший возможный радиус охватывающей сферы. Корсет – это небольшое подмножество, такое что α-аппроксимация решения на этом подмножестве является охватывающей сферой для всего множества. Корсет строится инкрементально, путем добавления в него самой удаленной точки на каждой итерации. Кумар и др. улучшили этот алгоритм аппроксимации, добившись времени работы O(n log n).

Точный решатель Фишера

Фишер и др. (2003) предложили точный решатель, однако алгоритм не гарантирует полиномиальное время работы в худшем случае. Алгоритм является чисто комбинаторным и реализует схему выбора опорного элемента, аналогичную методу симплекса для линейного программирования, которая ранее использовалась в некоторых эвристиках. Он начинается с большой сферы, охватывающей все точки, и постепенно уменьшает ее, пока дальнейшее уменьшение становится невозможным. Алгоритм включает корректные правила завершения работы в случаях вырождения, которые были пропущены предыдущими авторами, а также эффективную обработку частичных решений, что обеспечивает значительное ускорение. Авторы подтвердили, что алгоритм эффективен на практике в пространствах низкой и умеренно низкой (до 10 000) размерности и заявляют об отсутствии проблем с численной устойчивостью при операциях с плавающей точкой. Реализация алгоритма на C++ доступна как проект с открытым исходным кодом.

Крайние точки оптимальной сферы

предложил метод "оптимальной сферы экстремальных точек" с контролируемой скоростью сближения для достижения заданной точности при решении задачи нахождения ограничивающей сферы. Этот метод работает путем выбора набора направляющих векторов и проецирования всех точек на каждый из этих векторов; параметр служит для балансировки между скоростью и точностью. Точный решатель применяется к экстремальным точкам этих проекций. Затем алгоритм итеративно обрабатывает оставшиеся точки (если таковые имеются), расширяя сферу при необходимости. Для больших значений этот метод работает на несколько порядков быстрее точных методов, обеспечивая при этом сопоставимые результаты. Его худшее время выполнения составляет .