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

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

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

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

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

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

Приложения

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

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

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

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

Алгоритмы

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

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

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

В 1991 году Эмо Вельцль предложил гораздо более простой рандомизированный алгоритм, основанный на расширении алгоритма рандомизированного линейного программирования Раймундом Зайделем . Он работает с ожидаемым линейным временем. В статье представлены экспериментальные результаты, демонстрирующие его практичность в более высоких измерениях. ^[3]

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

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

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

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

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

Приближение на основе базового набора

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

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

Kumar et al. улучшил этот алгоритм аппроксимации ^[7], чтобы он работал во времени . ${\ Displaystyle О ({\ гидроразрыва {nd} {\ epsilon}} + {\ гидроразрыва {1} {\ epsilon ^ {4.5}}} \ log {\ frac {1} {\ epsilon}})}$

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

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

Экстремальные точки Оптимальная сфера

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

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

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

использованная литература

^ a b Ларссон, Томас (2008), "Быстро и плотно прилегающие ограничивающие сферы" , SIGRAD 2008: Ежегодная конференция SIGRAD, Специальная тема: Взаимодействие, 27-28 ноября 2008 г., Стокгольм, Швеция , Linköping Electronic Conference Proceedings, 34 , Линчёпинг, Швеция: Университет Линчёпинга
^ http://theory.stanford.edu/~megiddo/bio.html
^ Welzl, Эмо (1991), "Наименьшие ограждающих диски (шары и эллипсоиды)", в Maurer, Hermann, ( под ред.) Новые результаты и новые тенденции в области компьютерных наук: Грац, Австрия, 20-21 июня 1991 г., Сборник научных трудов ( PDF) , Lecture Notes в области компьютерных наук, 555 , Берлин, Германия: Springer., С. 359-370, DOI : 10.1007 / BFb0038202 , MR 1254721
^ CGAL 4.3 - Bounding Volumes - Min_sphere_of_spheres_d , получено 30 марта 2014 г.
^ Риттер, Джек (1990), «Эффективная ограничивающая сфера», в Гласснер, Эндрю С. (редактор), Graphics Gems , Сан-Диего, Калифорния, США: Academic Press Professional, Inc., стр. 301–303, ISBN 0-12-286166-3
^ Bādoiu Михай; Хар-Пелед, Сариэль ; Индик, Петр (2002), «Приближенная кластеризация с помощью базовых наборов» (PDF) , Труды тридцать четвертого ежегодного симпозиума ACM по теории вычислений , Нью-Йорк, штат Нью-Йорк, США: ACM, стр. 250–257, doi : 10.1145 / 509907.509947 , Руководство по ремонту 2121149 , S2CID 5409535
^ Кумар, Пиюш; Митчелл, Джозеф SB ; Йылдырым, Э. Альпер (2003), «Вычисление основных наборов и приближенных наименьших охватывающих гиперсфер в больших измерениях», в Ладнер, Ричард Э. (ред.), Труды Пятого семинара по разработке алгоритмов и экспериментам, Балтимор, Мэриленд, США, 11 января 2003 г. , Филадельфия, Пенсильвания, США: SIAM, стр. 45–55.
^ а б Фишер, Каспар; Гертнер, Бернд; Куц, Мартин (2003), «Быстрое вычисление наименьшего охватывающего шара в больших измерениях» (PDF) , в Баттисте, Джузеппе Ди; Цвик, Ури (ред.), Алгоритмы: ESA 2003, 11-й ежегодный европейский симпозиум, Будапешт, Венгрия, 16-19 сентября 2003 г., Proceedings (PDF) , Lecture Notes in Computer Science, 2832 , Springer, Berlin, pp. 630– 641, DOI : 10.1007 / 978-3-540-39658-1_57
^ проект с открытым исходным кодом miniball

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

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

[epos-1] Ларссон, Томас (2008), "Быстро и плотно прилегающие ограничивающие сферы" , SIGRAD 2008: Ежегодная конференция SIGRAD, Специальная тема: Взаимодействие, 27-28 ноября 2008 г., Стокгольм, Швеция , Linköping Electronic Conference Proceedings, 34 , Линчёпинг, Швеция: Университет Линчёпинга

[2] ttp://theory.stanford.edu/~megiddo/bio.html

[welzl92-3] Welzl, Эмо (1991), "Наименьшие ограждающих диски (шары и эллипсоиды)", в Maurer, Hermann, ( под ред.) Новые результаты и новые тенденции в области компьютерных наук: Грац, Австрия, 20-21 июня 1991 г., Сборник научных трудов ( PDF) , Lecture Notes в области компьютерных наук, 555 , Берлин, Германия: Springer., С. 359-370, DOI : 10.1007 / BFb0038202 , MR 1254721

[4] CGAL 4.3 - Bounding Volumes - Min_sphere_of_spheres_d , получено 30 марта 2014 г.

[Ritter1990-5] Риттер, Джек (1990), «Эффективная ограничивающая сфера», в Гласснер, Эндрю С. (редактор), Graphics Gems , Сан-Диего, Калифорния, США: Academic Press Professional, Inc., стр. 301–303, ISBN 0-12-286166-3

[Badoiu2002-6] Bādoiu Михай; Хар-Пелед, Сариэль ; Индик, Петр (2002), «Приближенная кластеризация с помощью базовых наборов» (PDF) , Труды тридцать четвертого ежегодного симпозиума ACM по теории вычислений , Нью-Йорк, штат Нью-Йорк, США: ACM, стр. 250–257, doi : 10.1145 / 509907.509947 , Руководство по ремонту 2121149 , S2CID 5409535

[kumar2003-7] Кумар, Пиюш; Митчелл, Джозеф SB ; Йылдырым, Э. Альпер (2003), «Вычисление основных наборов и приближенных наименьших охватывающих гиперсфер в больших измерениях», в Ладнер, Ричард Э. (ред.), Труды Пятого семинара по разработке алгоритмов и экспериментам, Балтимор, Мэриленд, США, 11 января 2003 г. , Филадельфия, Пенсильвания, США: SIAM, стр. 45–55.

[Fischer2003-8] а б Фишер, Каспар; Гертнер, Бернд; Куц, Мартин (2003), «Быстрое вычисление наименьшего охватывающего шара в больших измерениях» (PDF) , в Баттисте, Джузеппе Ди; Цвик, Ури (ред.), Алгоритмы: ESA 2003, 11-й ежегодный европейский симпозиум, Будапешт, Венгрия, 16-19 сентября 2003 г., Proceedings (PDF) , Lecture Notes in Computer Science, 2832 , Springer, Berlin, pp. 630– 641, DOI : 10.1007 / 978-3-540-39658-1_57

[9] проект с открытым исходным кодом miniball

[1]