Ограничивающая сфера - Википедия - Bounding sphere

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

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

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

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

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

Приложения

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

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

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

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

Алгоритмы

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

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

Нимрод Мегиддо широко изучали проблему 1-центра и публиковали по ней не менее пяти раз в 1980-х годах.[2] В 1983 году он предложил "обрезать и искать "алгоритм, который находит оптимальную ограничивающую сферу и работает за линейное время, если размерность фиксирована как константа. Когда размерность принимается во внимание, сложность времени выполнения составляет , непрактично для приложений большой размерности. Мегиддо использовал этот подход линейного программирования в линейном времени, когда размерность фиксирована.

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

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

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

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

  1. Выберите точку из , найдите точку в , имеющий наибольшее расстояние от ;
  2. Искать точку в , имеющий наибольшее расстояние от . Установить начальный мяч , с центром в середине и , радиус как половина расстояния между и ;
  3. Если все точки в находятся в пределах шара , то получаем ограничивающую сферу. В противном случае пусть быть точкой вне шара, построить новый шар, охватывающий обе точки и предыдущий бал. Повторяйте этот шаг, пока не будут покрыты все точки.

Алгоритм Риттера работает во времени на входах, состоящих из указывает в -мерное пространство, что делает его очень эффективным. Однако он дает только грубый результат, который обычно на 5-20% больше оптимального.[нужна цитата ]

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

Bădoiu et al. представил приближение к задаче об ограничивающей сфере,[6] где аппроксимация означает, что построенная сфера имеет радиус не более , куда - наименьший возможный радиус ограничивающей сферы.

А Coreset небольшое подмножество, что разложение решения на подмножество является ограничивающей сферой всего множества. Базовый набор создается постепенно путем добавления самой дальней точки в набор на каждой итерации.

Kumar et al. улучшил этот алгоритм приближения[7] чтобы он работал вовремя .

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

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

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

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

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

Рекомендации

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

внешняя ссылка