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

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

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

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

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

Приложения

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

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

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

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

Алгоритмы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

Ссылки

^ Jump up to: ^а ^б Ларссон, Томас (2008), «Быстрая и плотная подгонка ограничивающих сфер» , SIGRAD 2008: Ежегодная конференция SIGRAD, специальная тема: взаимодействие, 27–28 ноября 2008 г., Стокгольм, Швеция , Материалы электронной конференции в Линчёпинге, том. 34 года, Линчёпинг, Швеция: Университет Линчёпинга
^ «Резюме и публикации Нимрода Мегиддо» .
^ Мегиддо, Нимрод (1988). «Линейное программирование в линейное время при фиксированном размере» . Журнал АКМ . 33 (1): 114–147. дои : 10.1145/2422.322418 . S2CID 12686747 .
^ Jump up to: ^а ^б Чан, Тимоти (2018). «Улучшенные детерминированные алгоритмы линейного программирования в малых размерностях». Транзакции ACM на алгоритмах . 14 (3): Статья 30, 10 страниц. дои : 10.1145/3155312 . S2CID 9345339 .
^ Вельцль, Эмо (1991), «Наименьшие вмещающие диски (шары и эллипсоиды)», в книге Маурера, Германа (ред.), Новые результаты и новые тенденции в компьютерных науках: Грац, Австрия, 20–21 июня 1991 г., Труды , Лекция Заметки по информатике, том. 555, Берлин, Германия: Springer, стр. 359–370, doi : 10.1007/BFb0038202 , ISBN. 3-540-54869-6 , МР 1254721
^ CGAL 4.3 - Граничные объемы - Min_sphere_of_spheres_d , получено 30 марта 2014 г.
^ Jump up to: ^а ^б Риттер, Джек (1990), «Эффективная ограничивающая сфера», в Гласснер, Эндрю С. (редактор), Graphics Gems , Сан-Диего, Калифорния, США: Academic Press Professional, Inc., стр. 301–303, ISBN 0-12-286166-3
^ Бадою, Михай; Хар-Пелед, Сариэль ; Индик, Петр (2002), «Приблизительная кластеризация с помощью базовых наборов» (PDF) , Труды тридцать четвертого ежегодного симпозиума ACM по теории вычислений , Нью-Йорк, Нью-Йорк, США: ACM, стр. 250–257, CiteSeerX 10.1 .1.4.9395 , doi : 10.1145/509907.509947 , MR 2121149 , S2CID 5409535
^ Кумар, Пиюш; Митчелл, Джозеф С.Б .; Йылдырым, Э. Альпер (2003), «Вычислительные базовые наборы и приблизительные наименьшие вмещающие гиперсферы в больших измерениях», в Ладнер, Ричард Э. (ред.), Труды пятого семинара по разработке алгоритмов и экспериментам, Балтимор, Мэриленд, США, 11 января 2003 г. , Филадельфия, Пенсильвания, США: SIAM, стр. 45–55.
^ Jump up to: ^а ^б Фишер, Каспар; Гертнер, Бернд; Куц, Мартин (2003), «Быстрое вычисление наименьшего окружающего шара в больших размерностях» (PDF) , в Баттисте, Джузеппе Ди; Цвик, Ури (ред.), Алгоритмы: ESA 2003, 11-й ежегодный европейский симпозиум, Будапешт, Венгрия, 16–19 сентября 2003 г., Материалы (PDF) , Конспекты лекций по информатике, том. 2832, Springer, Берлин, стр. 630–641, номер документа : 10.1007/978-3-540-39658-1_57 , ISBN. 978-3-540-20064-2
^ проект с открытым исходным кодом мини-шара

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

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

[epos-1] Jump up to: ^а ^б Ларссон, Томас (2008), «Быстрая и плотная подгонка ограничивающих сфер» , SIGRAD 2008: Ежегодная конференция SIGRAD, специальная тема: взаимодействие, 27–28 ноября 2008 г., Стокгольм, Швеция , Материалы электронной конференции в Линчёпинге, том. 34 года, Линчёпинг, Швеция: Университет Линчёпинга

[2] «Резюме и публикации Нимрода Мегиддо» .

[meg88-3] Мегиддо, Нимрод (1988). «Линейное программирование в линейное время при фиксированном размере» . Журнал АКМ . 33 (1): 114–147. дои : 10.1145/2422.322418 . S2CID 12686747 .

[chan18-4] Jump up to: ^а ^б Чан, Тимоти (2018). «Улучшенные детерминированные алгоритмы линейного программирования в малых размерностях». Транзакции ACM на алгоритмах . 14 (3): Статья 30, 10 страниц. дои : 10.1145/3155312 . S2CID 9345339 .

[welzl92-5] Вельцль, Эмо (1991), «Наименьшие вмещающие диски (шары и эллипсоиды)», в книге Маурера, Германа (ред.), Новые результаты и новые тенденции в компьютерных науках: Грац, Австрия, 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 марта 2014 г.

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

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

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

[Fischer2003-10] Jump up to: ^а ^б Фишер, Каспар; Гертнер, Бернд; Куц, Мартин (2003), «Быстрое вычисление наименьшего окружающего шара в больших размерностях» (PDF) , в Баттисте, Джузеппе Ди; Цвик, Ури (ред.), Алгоритмы: ESA 2003, 11-й ежегодный европейский симпозиум, Будапешт, Венгрия, 16–19 сентября 2003 г., Материалы (PDF) , Конспекты лекций по информатике, том. 2832, Springer, Берлин, стр. 630–641, номер документа : 10.1007/978-3-540-39658-1_57 , ISBN. 978-3-540-20064-2

[11] проект с открытым исходным кодом мини-шара

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]