Ограничивающая сфера

Сфера, содержащая набор объектов

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

В математике , если задано непустое множество объектов конечной протяженности в -мерном пространстве , например, множество точек, ограничивающая сфера , объемлющая сфера или объемлющий шар для этого множества, то это -мерная сплошная сфера, содержащая все эти объекты. ${\displaystyle d}$ ${\displaystyle d}$

Ограничивающая сфера, используемая в компьютерной графике и вычислительной геометрии , является особым типом ограничивающего объема . Существует несколько быстрых и простых алгоритмов построения ограничивающей сферы, имеющих высокую практическую ценность в приложениях компьютерной графики в реальном времени. ^[1]

В статистике и исследовании операций объектами обычно являются точки, и, как правило, сфера интереса — это минимальная ограничивающая сфера , то есть сфера с минимальным радиусом среди всех ограничивающих сфер. Можно доказать, что такая сфера уникальна: если их две, то рассматриваемые объекты лежат внутри их пересечения. Но пересечение двух несовпадающих сфер одинакового радиуса содержится в сфере меньшего радиуса.

Задача вычисления центра минимальной ограничивающей сферы также известна как «невзвешенная евклидова задача об одном центре ».

Приложения

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

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

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

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

Алгоритмы

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

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

Нимрод Мегиддо подробно изучал проблему 1-центра и опубликовал по ней не менее пяти работ в 1980-х годах. ^[2] В 1983 году он предложил алгоритм « обрезки и поиска », который находит оптимальную ограничивающую сферу и работает за линейное время, если размерность фиксирована как константа. Если принять во внимание размерность, сложность времени выполнения составляет , ^{[3] [4]} что непрактично для приложений с высокой размерностью. ${\displaystyle d}$ ${\displaystyle O(2^{O(d^{2})}n)}$

В 1991 году Эмо Вельцль предложил гораздо более простой рандомизированный алгоритм , обобщающий рандомизированный алгоритм линейного программирования Раймунда Зайделя . Ожидаемое время работы алгоритма Вельцля составляет , что снова сводится к для любой фиксированной размерности . В статье приводятся экспериментальные результаты, демонстрирующие его практичность в более высоких размерностях. ^[5] Более поздний детерминированный алгоритм Тимоти Чана также работает во времени, с меньшей (но все еще экспоненциальной) зависимостью от размерности. ^[4] ${\displaystyle O((d+1)(d+1)!n)}$ ${\displaystyle O(n)}$ ${\displaystyle d}$ ${\displaystyle O(n)}$

Библиотека алгоритмов вычислительной геометрии с открытым исходным кодом (CGAL) содержит реализацию алгоритма Вельцла. ^[6]

Ограничивающая сфера Риттера

В 1990 году Джек Риттер предложил простой алгоритм для поиска неминимальной ограничивающей сферы. ^[7] Он широко используется в различных приложениях из-за своей простоты. Алгоритм работает следующим образом:

1. Выберите точку из , найдите точку в , которая находится на наибольшем расстоянии от ; ${\displaystyle x}$ ${\displaystyle P}$ ${\displaystyle y}$ ${\displaystyle P}$ ${\displaystyle x}$
2. Найдите точку в , которая находится на наибольшем расстоянии от . Установите начальный шар с центром в середине и , радиусом, равным половине расстояния между и ; ${\displaystyle z}$ ${\displaystyle P}$ ${\displaystyle y}$ ${\displaystyle B}$ ${\displaystyle y}$ ${\displaystyle z}$ ${\displaystyle y}$ ${\displaystyle z}$
3. Если все точки в находятся внутри шара , то мы получаем ограничивающую сферу. В противном случае, пусть будет точкой вне шара, строит новый шар, покрывающий как точку, так и предыдущий шар. Повторяйте этот шаг, пока все точки не будут покрыты. ${\displaystyle P}$ ${\displaystyle B}$ ${\displaystyle p}$ ${\displaystyle p}$

Алгоритм Риттера работает во времени на входных данных, состоящих из точек в -мерном пространстве, что делает его очень эффективным. Однако он дает только грубый результат, который обычно на 5–20 % больше оптимального. ^[7] ${\displaystyle O(nd)}$ ${\displaystyle n}$ ${\displaystyle d}$

Аппроксимация на основе набора ядер

Бадою и др. представили приближение к задаче ограничивающей сферы ^[8] , где приближение означает, что построенная сфера имеет радиус не более , где — наименьший возможный радиус ограничивающей сферы. ${\displaystyle 1+\varepsilon }$ ${\displaystyle 1+\varepsilon }$ ${\displaystyle (1+\varepsilon )r}$ ${\displaystyle r}$

Coreset — это небольшое подмножество, расширение решения на котором является ограничивающей сферой всего множества. Coreset строится постепенно, путем добавления самой дальней точки в множество в каждой итерации . ${\displaystyle 1+\varepsilon }$

Кумар и др. усовершенствовали этот алгоритм аппроксимации ^[9], так что он теперь работает со временем . ${\displaystyle O({\frac {nd}{\epsilon }}+{\frac {1}{\epsilon ^{4.5}}}\log {\frac {1}{\epsilon }})}$

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

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

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

Larsson (2008) предложил метод «оптимальной сферы экстремальных точек» с контролируемой скоростью приближения точности для решения проблемы ограничивающей сферы. Этот метод работает, беря набор векторов направления и проецируя все точки на каждый вектор в ; служит переменной компромисса скорости и точности. Точный решатель применяется к экстремальным точкам этих проекций. Затем алгоритм выполняет итерации по оставшимся точкам, если таковые имеются, увеличивая сферу при необходимости. Для больших этот метод на порядки быстрее точных методов, при этом давая сопоставимые результаты. Он имеет худшее время . ^[1] ${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle 2s}$ ${\displaystyle n}$ ${\displaystyle O(sn)}$

Смотрите также

• Ограничивающий объем
• Описанная сфера , описанная окружность

Ссылки

1. Larsson, Thomas (2008), "Быстро и плотно прилегающие ограничивающие сферы", SIGRAD 2008: Ежегодная конференция SIGRAD, Специальная тема: Взаимодействие, 27-28 ноября 2008 г., Стокгольм, Швеция , Linköping Electronic Conference Proceedings, том 34, Линчёпинг, Швеция: Университет Линчёпинга
2. «Резюме и публикации Нимрода Мегиддо».
3. Мегиддо, Нимрод (1988). «Линейное программирование за линейное время при фиксированной размерности». Журнал ACM . 33 (1): 114–147. doi : 10.1145/2422.322418 . S2CID  12686747.
4. Chan, Timothy (2018). «Улучшенные детерминированные алгоритмы для линейного программирования в низких размерностях». ACM Transactions on Algorithms . 14 (3): Статья 30, 10 страниц. doi : 10.1145/3155312. S2CID  9345339.
5. Welzl, Emo (1991), «Наименьшие охватывающие диски (шары и эллипсоиды)», в Maurer, Hermann (ред.), Новые результаты и новые тенденции в информатике: Грац, Австрия, 20–21 июня 1991 г., Труды, Заметки лекций по информатике, т. 555, Берлин, Германия: Springer, стр. 359–370, doi :10.1007/BFb0038202, ISBN 3-540-54869-6, МР  1254721
6. CGAL 4.3 — Ограничивающие объемы — Min_sphere_of_spheres_d, получено 30.03.2014.
7. Ritter, Jack (1990), «Эффективная ограничивающая сфера», в Glassner, Andrew S. (ред.), Graphics Gems , Сан-Диего, Калифорния, США: Academic Press Professional, Inc., стр. 301–303, ISBN 0-12-286166-3
8. Бадоиу, Михай; Хар-Пелед, Сариэль ; Индик, Петр (2002), «Приблизительная кластеризация с помощью основных наборов» (PDF) , Труды тридцать четвертого ежегодного симпозиума ACM по теории вычислений , Нью-Йорк, США: ACM, стр. 250–257, CiteSeerX 10.1.1.4.9395 , doi :10.1145/509907.509947, MR  2121149, S2CID  5409535 
9. Кумар, Пиюш; Митчелл, Джозеф СБ ; Йылдырым, Э. Альпер (2003), «Вычислительные наборы ядер и приближенные наименьшие охватывающие гиперсферы в больших размерностях», в Ladner, Ричард Э. (ред.), Труды Пятого семинара по разработке алгоритмов и экспериментам, Балтимор, Мэриленд, США, 11 января 2003 г. , Филадельфия, Пенсильвания, США: SIAM, стр. 45–55
10. Фишер, Каспар; Гертнер, Бернд; Куц, Мартин (2003), "Быстрое вычисление наименьшего охватывающего шара в больших размерностях" (PDF) , в Баттиста, Джузеппе Ди; Цвик, Ури (ред.), Алгоритмы: ESA 2003, 11-й ежегодный европейский симпозиум, Будапешт, Венгрия, 16-19 сентября 2003 г., Труды (PDF) , Lecture Notes in Computer Science, т. 2832, Springer, Берлин, стр. 630–641, doi :10.1007/978-3-540-39658-1_57, ISBN 978-3-540-20064-2
11. проект с открытым исходным кодом miniball

Внешние ссылки

• Задача о наименьшем ограничивающем круге – описывает несколько алгоритмов для ограничения множества точек, включая алгоритм Мегиддо с линейным временем.