Задача наименьшего круга
Задача наименьшего круга (также известная как проблема минимального охватывающего круга , ограничивающего круга , проблема наименьшего ограничивающего круга , проблема наименьшего охватывающего круга ) — это задача вычислительной геометрии , заключающаяся в вычислении наименьшего круга , который содержит все заданный набор точек проблема в евклидовом пространстве. самолет . Соответствующая проблема в n -мерном пространстве , проблема наименьшей ограничивающей сферы , состоит в вычислении наименьшей n -сферы , содержащей весь заданный набор точек. [1] Задача о наименьшем круге была первоначально предложена английским математиком Джеймсом Джозефом Сильвестром в 1857 году. [2]
Задача о наименьшем круге на плоскости является примером проблемы размещения объекта ( задача 1 центра ), в которой необходимо выбрать местоположение нового объекта для обслуживания нескольких клиентов, минимизируя самое дальнее расстояние, на которое может рассчитывать любой клиент. должен отправиться в путь, чтобы добраться до нового объекта. [3] И проблема наименьшего круга на плоскости, и проблема наименьшей ограничивающей сферы в любом многомерном пространстве ограниченной размерности разрешимы в худшем случае за линейное время .
Характеристика
[ редактировать ]Большинство геометрических подходов к решению проблемы ищут точки, лежащие на границе минимального круга, и основаны на следующих простых фактах:
- Минимальный охватывающий круг уникален.
- Минимальная покрывающая окружность множества S может быть определена не более чем тремя точками из S , лежащими на границе окружности. Если он определяется только двумя точками, то отрезок линии, соединяющий эти две точки, должен иметь диаметр минимального круга. Если он определяется тремя точками, то треугольник, состоящий из этих трех точек, не является тупоугольным .
Доказательство единственности минимального покрывающего диска.
|
---|
Линейные решения
[ редактировать ]Как показал Нимрод Мегиддо , [5] минимальный охватывающий круг можно найти за линейное время, и та же граница линейного времени применима и к наименьшей охватывающей сфере в евклидовых пространствах любой постоянной размерности. В его статье также дается краткий обзор более ранних и алгоритмы; [6] при этом Мегиддо продемонстрировал, что гипотеза Шамоса и Хоуи о том, что решение задачи наименьшего круга можно вычислить в в лучшем случае – было ложным. [7]
Эмо Вельцль [8] предложил простой рандомизированный алгоритм для Задача о минимальном охватывающем круге, которая выполняется в ожидаемое время , основанный на линейного программирования алгоритме Раймунда Зейделя .
Впоследствии задача о наименьшем круге была включена в общий класс задач типа ЛП , которые можно решить с помощью алгоритмов, подобных алгоритму Вельцля, основанных на линейном программировании. Как следствие принадлежности к этому классу было показано, что зависимость от размерности постоянного множителя в Ограничение по времени, которое было факториалом для метода Зейделя, можно было свести к субэкспоненциальному . [6]
Алгоритм Мегиддо
[ редактировать ]Алгоритм Мегиддо [9] основан на методе обрезки и поиска, уменьшающем размер проблемы путем удаления ненужные моменты. Это приводит к рецидивам предоставление .
Алгоритм достаточно сложен, о чем свидетельствует его большая мультипликативная константа. При сокращении необходимо дважды решить аналогичную задачу, в которой центр искомой охватывающей окружности должен лежать на заданной прямой . Решением подзадачи является либо решение безусловной задачи, либо оно используется для определения полуплоскости, в которой расположен центр неограниченного решения.
The точки, подлежащие отбрасыванию, находятся следующим образом: Точки Pi определяет разбиты на пары, что линии pj являются их биссектрисами . Находят медианное среднее pm p биссектрис в порядке их направлений (ориентированных на одну и ту же полуплоскость, определяемую биссектрисой 1 ) и составляют пары биссектрис так, что в каждой паре одна биссектриса имеет направление не более pm а , другое, по крайней мере, после полудня (направление p 1 можно рассматривать как — или + в соответствии с нашими потребностями.) Пусть Q k — пересечение биссектрис в k -й паре.
Прямая q в направлении p 1 проходит через пересечение Q x такое, что существуют пересечения в каждой полуплоскости, определяемые линией (срединное положение). Ограниченная версия охватывающей задачи выполняется на линии q', которая определяет полуплоскость, в которой расположен центр. Прямая q ' в pm направлении проходит через пересечение Q x' такое, что существуют пересечения в каждой половине полуплоскости, не содержащей решения. Ограниченная версия охватывающей задачи выполняется на линии q ′, которая вместе с q определяет квадрант, в котором расположен центр. Рассмотрим точки Qk . в квадранте, не входящие в полуплоскость, содержащую решение Одна из биссектрис пары, определяющей Q k, имеет направление, обеспечивающее, какая из точек Pi , определяющих биссектрису, находится ближе к каждой точке квадранта, содержащего центр охватывающей окружности. Этот пункт можно было бы отбросить.
Ограниченная версия алгоритма также решается методом сокращения и поиска, но размер задачи уменьшается за счет удаления моменты, ведущие к рецидиву
предоставление .
The точки, подлежащие отбрасыванию, находятся следующим образом: Точки P i располагаются попарно. пересечение Q j ее биссектрисы с ограничивающей прямой q Для каждой пары находится (если этого пересечения не существует, мы могли бы сразу удалить одну точку из пары). медиана M точек Q j на прямой q Находится и за время O ( n ) определяется, какая полулиния q начинается в M содержит решение ограниченной задачи. Рассмотрим точки Q j со второй половины. Мы знаем, какая из точек Pi , определяющих Q j, находится ближе к каждой точке полупрямой, содержащей центр охватывающей окружности решения задачи с ограничениями. Этот пункт можно было бы отбросить.
Полуплоскость, в которой лежит неограниченное решение, может быть определена точками P i на границе ограниченного кругового решения. (Достаточно первой и последней точки круга в каждой полуплоскости. Если центр принадлежит их выпуклой оболочке , это неограниченное решение, в противном случае направление к ближайшему ребру определяет полуплоскость неограниченного решения.)
Алгоритм Вельцля
[ редактировать ]Алгоритм рекурсивный .
Исходным входом является набор P точек. Алгоритм выбирает одну точку p случайным образом и равномерно из P и рекурсивно находит минимальный круг, содержащий P – { p }, то есть все остальные точки в P, кроме p . Если возвращенный круг также включает в себя p , это минимальный круг для всего P и он возвращается.
В противном случае точка p должна лежать на границе результирующего круга. Он рекурсивный, но с набором R точек, которые, как известно, находятся на границе, в качестве дополнительного параметра.
Рекурсия завершается, когда P пуста точек , и решение может быть найдено из точек в R : для 0 или 1 точки решение тривиально, для 2 точек минимальный круг имеет центр в средней точке между двумя точками, а для 3 точки окружность — это описанная окружность треугольника, описанного точками. (В трех измерениях 4 точки требуют расчета описанной тетраэдра . сферы )
Рекурсия также может завершиться, когда R имеет размер 3 (в 2D или 4 в 3D), поскольку оставшиеся точки в P должны лежать внутри круга, описываемого R .
algorithm welzl is[8] input: Finite sets P and R of points in the plane |R| ≤ 3. output: Minimal disk enclosing P with R on the boundary. if P is empty or |R| = 3 then return trivial(R) choose p in P (randomly and uniformly) D := welzl(P − {p}, R) if p is in D then return D return welzl(P − {p}, R ∪ {p})
В статье Вельцля говорится, что достаточно случайно переставить входные данные в начале, а не выполнять независимый случайный выбор p в каждой рекурсии.
В нем также говорится, что производительность повышается за счет динамического изменения порядка точек, так что те точки, которые оказываются за пределами круга, впоследствии рассматриваются раньше, но это требует изменения в структуре алгоритма для хранения P как «глобального».
Другие алгоритмы
[ редактировать ]До того, как результат Мегиддо показал, что задача наименьшего круга может быть решена за линейное время, в литературе появилось несколько алгоритмов более высокой сложности. Наивный алгоритм решает задачу за время O( n 4 ) путем проверки окружностей, определяемых всеми парами и тройками точек.
- Алгоритм Кристала и Пирса применяет стратегию локальной оптимизации , которая сохраняет две точки на границе охватывающего круга и неоднократно сжимает круг, заменяя пару граничных точек, пока не будет найден оптимальный круг. Чакраборти и Чаудхури [10] предложить метод линейного времени для выбора подходящей начальной окружности и пары граничных точек на этой окружности. Каждый шаг алгоритма включает в себя в качестве одной из двух граничных точек новую вершину выпуклой оболочки , поэтому, если оболочка имеет h вершин, этот метод можно реализовать для выполнения за время O( nh ).
- Эльзинга и Хирн [11] описал алгоритм, который поддерживает охватывающий круг для подмножества точек. На каждом шаге точка, не покрытая текущей сферой, используется для поиска более крупной сферы, охватывающей новое подмножество точек, включая найденную точку. Хотя в худшем случае время работы составляет O( h 3 n ), авторы сообщают, что в их экспериментах он работал в линейном времени. Сложность метода была проанализирована Дрезнером и Шелой. [12] Коды как на Фортране , так и на языке C доступны у Hearn, Vijay & Nickel (1995) . [13]
- Задачу наименьшей сферы можно сформулировать в виде квадратичной программы. [1] определяется системой линейных ограничений с выпуклой квадратичной целевой функцией. Следовательно, любой возможный алгоритм направления может дать решение проблемы. [14] Хирн и Виджай [15] доказал, что подход допустимого направления, выбранный Якобсеном, эквивалентен алгоритму Кристалла – Пирса.
- Двойственная этой квадратичной программе также может быть сформулирована явно; [16] алгоритм Лоусона [17] таким образом можно описать как основной двойственный алгоритм. [15]
- Шамос и Хоуи [7] предложил алгоритм времени O( n log n ) для этой проблемы, основанный на наблюдении, что центр наименьшего охватывающего круга должен быть вершиной диаграммы Вороного самой дальней точки входного набора точек.
Взвешенные варианты задачи
[ редактировать ]Взвешенная версия задачи о минимальном охватывающем круге принимает в качестве входных данных набор точек в евклидовом пространстве, каждая из которых имеет веса; цель состоит в том, чтобы найти единственную точку, которая минимизирует максимальное взвешенное расстояние (т. е. расстояние, умноженное на соответствующий вес) до любой точки. Исходная (невзвешенная) задача о минимальном охватывающем круге соответствует случаю, когда все веса равны 1. Как и невзвешенная задача, взвешенная задача может быть решена за линейное время в любом пространстве ограниченной размерности, используя подходы, тесно связанные с ограниченной размерностью. алгоритмы линейного программирования, хотя в литературе снова часто встречаются более медленные алгоритмы. [15] [18] [19]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Jump up to: а б Эльзинга, Дж.; Хирн, Д.В. (1972), «Проблема минимальной покрывающей сферы», Management Science , 19 : 96–104, doi : 10.1287/mnsc.19.1.96.
- ^ Сильвестр, Дж. Дж. (1857), «Вопрос геометрии положения», Ежеквартальный журнал математики , 1 : 79 .
- ^ Фрэнсис, РЛ; Макгиннис, LF; Уайт, Дж. А. (1992), Планировка и расположение объекта: аналитический подход (2-е изд.), Энглвуд Клиффс, Нью-Джерси: Prentice–Hall, Inc.
- ^ Вельцль 1991 , с. 2.
- ^ Мегиддо, Нимрод (1983), «Алгоритмы линейного времени для линейного программирования в R 3 и связанные с ним проблемы», SIAM Journal on Computing , 12 (4): 759–776, doi : 10.1137/0212052 , MR 0721011 , S2CID 14467740 .
- ^ Jump up to: а б Матушек, Иржи ; Шарир, Миша ; Вельцль, Эмо (1996), граница для линейного программирования» (PDF) , Algorithmica , 16 (4–5):498–516, 10.1.1.46.5644 , doi : 10.1007 /BF01940877 , S2CID « Субэкспоненциальная CiteSeerX
- ^ Jump up to: а б Шамос, Мичиган ; Хоуи, Д. (1975), «Проблемы ближайшей точки», Труды 16-го ежегодного симпозиума IEEE по основам информатики , стр. 151–162, doi : 10.1109/SFCS.1975.8 , S2CID 40615455
- ^ Jump up to: а б Вельцль, Эмо (1991), «Наименьшие вмещающие диски (шары и эллипсоиды)», в Маурере, Х. (ред.), Новые результаты и новые тенденции в информатике , Конспекты лекций по информатике, том. 555, Springer-Verlag, стр. 359–370, CiteSeerX 10.1.1.46.1450 , doi : 10.1007/BFb0038202 , ISBN 978-3-540-54869-0 .
- ^ Мегиддо, Нимрод (1983), «Алгоритмы линейного времени для линейного программирования в R 3 и связанные с ним проблемы», SIAM Journal on Computing , 12 (4): 759–776, doi : 10.1137/0212052 , MR 0721011 , S2CID 14467740 .
- ^ Чакраборти, РК; Чаудхури, ПК (1981), «Заметки о геометрических решениях некоторых минимаксных задач определения местоположения», Transportation Science , 15 (2): 164–166, doi : 10.1287/trsc.15.2.164 .
- ^ Эльзинга, Дж.; Хирн, Д.В. (1972), «Геометрические решения некоторых минимаксных задач определения местоположения», Transportation Science , 6 (4): 379–394, doi : 10.1287/trsc.6.4.379 .
- ^ Дрезнер, Цви; Шела, Сахарон (1987), «О сложности алгоритма Эльзинги-Хирна для задачи 1 центра», Mathematics of Operations Research , 12 (2): 255–261, doi : 10.1287/moor.12.2.255 , JSTOR 3689688 .
- ^ Хирн, Д.В.; Виджай, Дж.; Никель, С. (1995), «Коды геометрических алгоритмов для (взвешенной) задачи минимального круга», European Journal of Operational Research , 80 : 236–237, doi : 10.1016/0377-2217(95)90075-6 .
- ^ Якобсен, С.К. (1981), «Алгоритм для минимаксной задачи Вебера», European Journal of Operational Research , 6 (2): 144–148, doi : 10.1016/0377-2217(81)90200-9 .
- ^ Jump up to: а б с Хирн, Д.В.; Виджей, Дж. (1982), «Эффективные алгоритмы для (взвешенной) задачи минимального круга», Operations Research , 30 (4): 777–795, doi : 10.1287/opre.30.4.777 .
- ^ Эльзинга, Дж.; Хирн, Д.В.; Рэндольф, У. Д. (1976), «Минимаксное расположение нескольких объектов с евклидовыми расстояниями», Transportation Science , 10 (4): 321–336, doi : 10.1287/trsc.10.4.321 .
- ^ Лоусон, CL (1965), «Наименьший покрывающий конус или сфера», SIAM Review , 7 (3): 415–417, doi : 10.1137/1007084 .
- ^ Мегиддо, Н. (1983), «Взвешенная евклидова задача с 1 центром», Математика исследования операций , 8 (4): 498–504, doi : 10.1287/moor.8.4.498 .
- ^ Мегиддо, Н. ; Земель, Э. (1986), « Алгоритм рандомизации O ( n log n ) для взвешенной евклидовой задачи с 1 центром», Journal of Algorithms , 7 (3): 358–368, doi : 10.1016/0196-6774 (86 )90027-1 .
Внешние ссылки
[ редактировать ]- Самый маленький код закрывающего шара Бернда Гертнера
- CGAL — пакет Min_sphere_of_spheres Библиотеки алгоритмов вычислительной геометрии (CGAL).
- Miniball - реализация алгоритма с открытым исходным кодом для решения задачи наименьшего охватывающего шара для малых и умеренно высоких размерностей.