В математике дано непустое множество объектов конечного расширения в-мерное пространство , например набор точек, ограничивающая сфера , охватывающая сфера или охватывающий шар для этого набора, является-мерная твердая сфера, содержащая все эти объекты.
Ограничивающая сфера, используемая в компьютерной графике и вычислительной геометрии , представляет собой особый тип ограничивающего объема . Существует несколько быстрых и простых алгоритмов построения ограничивающей сферы, имеющих высокую практическую ценность в приложениях компьютерной графики в реальном времени. [1]
В статистике и исследовании операций объекты обычно являются точками, и обычно сфера интереса - это минимальная ограничивающая сфера , то есть сфера с минимальным радиусом среди всех ограничивающих сфер. Можно доказать, что такая сфера уникальна: если их два, то рассматриваемые объекты лежат в пределах их пересечения. Но пересечение двух несовпадающих сфер равного радиуса содержится в сфере меньшего радиуса.
Проблема вычисления центра минимальной ограничивающей сферы также известна как «невзвешенная проблема евклидова 1-центра ».
Приложения
Кластеризация
Такие сферы полезны при кластеризации , когда группы одинаковых точек данных классифицируются вместе.
В статистическом анализе рассеяние из точек данных в пределах сферы может быть отнесено к погрешности измерения или естественным (обычно тепловым процессам), в этом случае кластер представляет собой возмущение точки идеала. В некоторых случаях эта идеальная точка может использоваться вместо точек в кластере, что позволяет сократить время вычислений.
В исследовании операций кластеризация значений до идеальной точки также может использоваться для уменьшения количества входных данных с целью получения приблизительных значений для NP-сложных задач за разумное время. Выбранная точка обычно не является центром сферы, так как это может быть смещено из-за выбросов, но вместо этого вычисляется некоторая форма среднего местоположения, такая как точка наименьших квадратов, для представления кластера.
Алгоритмы
Существуют точный и приближенный алгоритмы решения задачи об ограничивающей сфере.
Линейное программирование
Нимрод Мегиддо всесторонне изучал проблему одного центра и публиковал по ней по крайней мере пять раз в 1980-х годах. [2] В 1983 году он предложил алгоритм « отсечения и поиска », который находит оптимальную ограничивающую сферу и работает за линейное время, если размерность фиксирована как константа. С учетом размерности сложность времени выполнения составляет, непрактично для приложений большой размерности. Мегиддо использовал этот подход линейного программирования в линейном времени, когда размерность фиксирована.
В 1991 году Эмо Вельцль предложил гораздо более простой рандомизированный алгоритм, основанный на расширении алгоритма рандомизированного линейного программирования Раймундом Зайделем . Он работает с ожидаемым линейным временем. В статье представлены экспериментальные результаты, демонстрирующие его практичность в более высоких измерениях. [3]
Библиотека алгоритмов вычислительной геометрии (CGAL) с открытым исходным кодом содержит реализацию этого алгоритма. [4]
Ограничивающая сфера Риттера
В 1990 году Джек Риттер предложил простой алгоритм поиска неминимальной ограничивающей сферы. [5] Он широко используется в различных приложениях из-за своей простоты. Алгоритм работает так:
- Выберите точку из , найдите точку в , который имеет наибольшее расстояние от ;
- Искать точку в , который имеет наибольшее расстояние от . Установите начальный мяч, с центром в середине а также , радиус как половина расстояния между а также ;
- Если все точки в находятся в пределах шара , то получим ограничивающую сферу. В противном случае пусть быть точкой вне шара, построить новый шар, покрывающий обе точки и предыдущий бал. Повторяйте этот шаг, пока не будут покрыты все точки.
Алгоритм Риттера работает во времени на входах, состоящих из указывает в -мерное пространство, что делает его очень эффективным. Однако это дает только грубый результат, который обычно на 5-20% больше оптимального. [ необходима цитата ]
Приближение на основе базового набора
Bădoiu et al. представилприближение к задаче об ограничивающей сфере, [6] где a аппроксимация означает, что построенная сфера имеет радиус не более , где - наименьший возможный радиус ограничивающей сферы.
Coreset небольшое подмножество, чторазложение решения на подмножество является ограничивающей сферой всего множества. Базовый набор создается постепенно путем добавления самой дальней точки в набор на каждой итерации.
Kumar et al. улучшил этот алгоритм приближения [7], чтобы он работал во времени.
Точный решатель Фишера
Fischer et al. (2003) предложили точный решатель, хотя алгоритм не имеет полиномиального времени работы в худшем случае. [8] Алгоритм чисто комбинаторные и реализует схему поворотное аналогично симплекс - метода для линейного программирования , используемый ранее в некоторых эвристики. Он начинается с большой сферы, которая покрывает все точки и постепенно сжимается до тех пор, пока не станет невозможной. Алгоритм содержит правильные правила завершения в случаях вырождения, упущенного предыдущими авторами; и эффективное управление частичными решениями, что значительно ускоряет работу. Авторы подтвердили, что алгоритм эффективен на практике в малых и умеренно малых (до 10 000) измерениях, и утверждают, что он не проявляет проблем с числовой стабильностью при операциях с плавающей запятой. [8] Реализация алгоритма на C ++ доступна как проект с открытым исходным кодом. [9]
Экстремальные точки Оптимальная сфера
Ларссон (2008) предложил метод «оптимальной сферы с экстремальными точками» с управляемым приближением скорости к точности для решения задачи об ограничивающей сфере. Этот метод работает, если взять набор векторов направления и проецирования всех точек на каждый вектор в ; служит компромиссной переменной скорости и точности. Точный решатель применяется кэкстремальные точки этих проекций. Затем алгоритм перебирает оставшиеся точки, если таковые имеются, при необходимости увеличивая сферу. Для большихэтот метод на порядки быстрее точных методов, но дает сопоставимые результаты. Это худшее время. [1]
Смотрите также
Рекомендации
- ^ a b Ларссон, Томас (2008), «Быстро и плотно прилегающие ограничивающие сферы» , SIGRAD 2008: Ежегодная конференция SIGRAD, Специальная тема: Взаимодействие, 27-28 ноября 2008 г., Стокгольм, Швеция , Linköping Electronic Conference Proceedings, 34 , Линчёпинг, Швеция: Университет Линчёпинга
- ^ http://theory.stanford.edu/~megiddo/bio.html
- ^ Welzl, Emo (1991), «Наименьшие окружающие диски (шары и эллипсоиды)», в Maurer, Hermann (ed.), New Results and New Trends in Computer Science: Graz, Austria, 20–21 июня 1991 г., Proceedings (PDF ) , Lecture Notes в области компьютерных наук, 555 , Берлин, Германия: Springer., С. 359-370, DOI : 10.1007 / BFb0038202 , MR 1254721 CS1 maint: обескураженный параметр ( ссылка )
- ^ 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
- ^ Бадою, Михай; Хар-Пелед, Сариэль ; Индик, Петр (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
Внешние ссылки
- Задача наименьшего окружающего круга - описывает несколько алгоритмов замкнутого набора точек, включая алгоритм линейного времени Мегиддо.