Jump to content

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

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

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

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

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

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

Приложения

[ редактировать ]

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

[ редактировать ]

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

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

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

Алгоритмы

[ редактировать ]

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

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

[ редактировать ]

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

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

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

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

[ редактировать ]

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

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

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

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

[ редактировать ]

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

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

Кумар и др. улучшил этот алгоритм аппроксимации [9] чтобы оно шло вовремя .

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

[ редактировать ]

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

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

[ редактировать ]

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

См. также

[ редактировать ]
  1. ^ Jump up to: а б Ларссон, Томас (2008), «Быстрая и плотная подгонка ограничивающих сфер» , SIGRAD 2008: Ежегодная конференция SIGRAD, специальная тема: взаимодействие, 27–28 ноября 2008 г., Стокгольм, Швеция , Материалы электронной конференции в Линчёпинге, том. 34 года, Линчёпинг, Швеция: Университет Линчёпинга
  2. ^ «Резюме и публикации Нимрода Мегиддо» .
  3. ^ Мегиддо, Нимрод (1988). «Линейное программирование в линейное время при фиксированном размере» . Журнал АКМ . 33 (1): 114–147. дои : 10.1145/2422.322418 . S2CID   12686747 .
  4. ^ Jump up to: а б Чан, Тимоти (2018). «Улучшенные детерминированные алгоритмы линейного программирования в малых размерностях». Транзакции ACM на алгоритмах . 14 (3): Статья 30, 10 страниц. дои : 10.1145/3155312 . S2CID   9345339 .
  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 г.
  7. ^ Jump up to: а б Риттер, Джек (1990), «Эффективная ограничивающая сфера», в Гласснер, Эндрю С. (редактор), 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), «Вычислительные базовые наборы и приблизительные наименьшие вмещающие гиперсферы в больших измерениях», в Ладнер, Ричард Э. (ред.), Труды пятого семинара по разработке алгоритмов и экспериментам, Балтимор, Мэриленд, США, 11 января 2003 г. , Филадельфия, Пенсильвания, США: SIAM, стр. 45–55.
  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. ^ проект с открытым исходным кодом мини-шара
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: a87fecb999b7887e2e912102a41b4b51__1721864100
URL1:https://arc.ask3.ru/arc/aa/a8/51/a87fecb999b7887e2e912102a41b4b51.html
Заголовок, (Title) документа по адресу, URL1:
Bounding sphere - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)