Задача о наименьшем круге

Задача о наименьшей окружности ( также известная как задача о минимальной покрывающей окружности , задача о ограничивающей окружности , задача о наименьшей ограничивающей окружности , задача о наименьшей охватывающей окружности ) — это задача вычислительной геометрии по вычислению наименьшей окружности , содержащей все заданные множества точек на евклидовой плоскости . Соответствующая задача в n -мерном пространстве , задача о наименьшей ограничивающей сфере , заключается в вычислении наименьшей n -сферы , содержащей все заданные множества точек. ^[1] Задача о наименьшей окружности была первоначально предложена английским математиком Джеймсом Джозефом Сильвестром в 1857 году. ^[2]

Задача о наименьшем круге на плоскости является примером задачи о размещении объекта ( задача с одним центром ), в которой местоположение нового объекта должно быть выбрано таким образом, чтобы обеспечить обслуживание определенного количества клиентов, минимизируя наибольшее расстояние, которое должен преодолеть любой клиент, чтобы добраться до нового объекта. ^[3] Как задача о наименьшем круге на плоскости, так и задача о наименьшей ограничивающей сфере в любом многомерном пространстве ограниченной размерности разрешимы за наихудшее линейное время .

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

• Минимальный покрывающий круг единственен.
• Минимальная охватывающая окружность множества S может быть определена не более чем тремя точками в S , лежащими на границе окружности. Если она определяется только двумя точками, то отрезок прямой, соединяющий эти две точки, должен быть диаметром минимальной окружности. Если она определяется тремя точками, то треугольник, состоящий из этих трех точек, не является тупоугольным .

Как показал Нимрод Мегиддо , ^[5] минимальная охватывающая окружность может быть найдена за линейное время, и та же самая линейная временная граница применима также к наименьшей охватывающей сфере в евклидовых пространствах любой постоянной размерности. Его статья также дает краткий обзор более ранних и алгоритмов; ^[6] при этом Мегиддо продемонстрировал, что гипотеза Шамоса и Хоя — о том, что решение задачи наименьшей окружности вычислимо в лучшем случае за — была ложной. ^[7]${\displaystyle O(n^{3})}$${\displaystyle O(n\log n)}$${\displaystyle \Omega (n\log n)}$

Эмо Вельцль ^[8] предложил простой рандомизированный алгоритм для задачи минимального покрывающего круга, который выполняется за ожидаемое время , основанный на алгоритме линейного программирования Раймунда Зайделя .${\displaystyle O(n)}$

Впоследствии задача наименьшего круга была включена в общий класс задач типа LP , которые могут быть решены такими алгоритмами, как алгоритм Вельцля, основанный на линейном программировании. Вследствие принадлежности к этому классу было показано, что зависимость от размерности постоянного множителя в ограничении по времени, которая была факториальной для метода Зейделя, может быть сведена к субэкспоненциальной . ^[6] Алгоритм минидиска Вельцля был расширен для обработки расхождений Брегмана ^[9] , которые включают квадрат евклидова расстояния.${\displaystyle O(n)}$

Алгоритм Мегиддо ^[10] основан на технике, называемой обрезкой и поиском, уменьшающей размер проблемы путем удаления ненужных точек. Это приводит к повторению, дающему .${\textstyle {\frac {n}{16}}}$${\displaystyle t(n)\leq t\left({\frac {15n}{16}}\right)+cn}$${\displaystyle t(n)=16cn}$

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

Точки , которые следует отбросить, находятся следующим образом: Точки P _i объединяются в пары, которые определяют прямые p _j как их биссектрисы . Находится медианное среднее p _m биссектрис в порядке их направлений (ориентированных на одну и ту же полуплоскость, определяемую биссектрисой p ₁ ), и составляются пары биссектрис таким образом, что в каждой паре одна биссектриса имеет направление не более p _m , а другая не менее p _m (направление p ₁ можно рассматривать как − или + в зависимости от наших потребностей.) Пусть Q _k будет пересечением биссектрис в k -й паре.${\textstyle {\frac {n}{16}}}$${\textstyle {\frac {n}{2}}}$${\displaystyle \infty}$${\displaystyle \infty}$

Прямая q в направлении p ₁ помещается так, чтобы проходить через пересечение Q _x таким образом, чтобы в каждой полуплоскости, определяемой прямой, имелись пересечения (срединное положение). Ограниченная версия объемлющей задачи выполняется на прямой q', которая определяет полуплоскость, в которой расположен центр. Прямая q ′ в направлении p _m помещается так, чтобы проходить через пересечение Q _x' таким образом, чтобы в каждой половине полуплоскости, не содержащей решения, имелись пересечения. Ограниченная версия объемлющей задачи выполняется на прямой q ′, которая вместе с q определяет квадрант, в котором расположен центр. Мы рассматриваем точки Q _k в квадранте, не содержащемся в полуплоскости, содержащей решение. Одна из биссектрис пары, определяющей Q _k, имеет направление, гарантирующее, какая из точек P _{i ,} определяющих биссектрису, находится ближе к каждой точке в квадранте, содержащем центр объемлющей окружности. Эту точку можно отбросить.${\textstyle {\frac {n}{8}}}$${\textstyle {\frac {n}{16}}}$

Ограниченная версия алгоритма также решается методом отсечения и поиска, но с уменьшением размера задачи за счет удаления точек, приводящих к повторению.${\textstyle {\frac {n}{4}}}$

${\displaystyle t(n)\leq t\left({\frac {3n}{4}}\right)+cn}$

давая .${\displaystyle t(n)=4cn}$

Точки , которые нужно отбросить, находятся следующим образом: Точки P _i объединяются в пары. Для каждой пары находится пересечение Q _j ее биссектрисы с ограничивающей прямой q (Если этого пересечения не существует, мы могли бы немедленно удалить одну точку из пары). Находится медиана M точек Q _j на прямой q и за время O ( n ) определяется, какая полупрямая q, начинающаяся в M, содержит решение ограниченной задачи. Мы рассматриваем точки Q _j из другой половины. Мы знаем, какая из точек P _i, определяющих Q _j, находится ближе к каждой точке полупрямой, содержащей центр охватывающей окружности решения ограниченной задачи. Эту точку можно отбросить.${\textstyle {\frac {n}{4}}}$

Полуплоскость, в которой лежит решение без ограничений, может быть определена точками 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.

Алгоритм welzl [8] : входные данные: конечные множества P и R точек на плоскости | R | ≤ 3. выходные данные: минимальный диск, охватывающий P с R на границе.  если  P пусто или | R | = 3 , то  вернуть trivial( R ) выбрать  p из P ( случайным образом и равномерно ) D := welzl( P − { p }, R ) если  p находится в D,  то  вернуть  D вернуть welzl( P − { p }, R ∪ { p })

В статье Вельцля утверждается, что достаточно случайным образом переставлять входные данные в начале, а не выполнять независимый случайный выбор p в каждой рекурсии.

В нем также говорится, что производительность повышается за счет динамического переупорядочивания точек, так что те, которые оказываются за пределами круга, впоследствии рассматриваются раньше, но это требует изменения структуры алгоритма для сохранения P как «глобального».

До результата Мегиддо, показывающего, что задача наименьшего круга может быть решена за линейное время, в литературе появилось несколько алгоритмов более высокой сложности. Наивный алгоритм решает задачу за время O( n ⁴ ) путем проверки кругов, определяемых всеми парами и тройками точек.

• Алгоритм Кристала и Пирса применяет стратегию локальной оптимизации , которая сохраняет две точки на границе охватывающего круга и многократно сжимает круг, заменяя пару граничных точек, пока не будет найден оптимальный круг. Чакраборти и Чаудхури ^[11] предлагают метод линейного времени для выбора подходящего начального круга и пары граничных точек на этом круге. Каждый шаг алгоритма включает в качестве одной из двух граничных точек новую вершину выпуклой оболочки , поэтому, если оболочка имеет h вершин, этот метод может быть реализован для выполнения за время O( nh ).
• Элзинга и Хирн ^[12] описали алгоритм, который поддерживает покрывающую окружность для подмножества точек. На каждом шаге точка, не покрытая текущей сферой, используется для поиска большей сферы, которая покрывает новое подмножество точек, включая найденную точку. Хотя в худшем случае время выполнения составляет O( h ³ n ), авторы сообщают, что в их экспериментах он работал за линейное время. Сложность метода была проанализирована Дрезнером и Шелахом. ^[13] Коды на Фортране и С доступны в Hearn, Vijay & Nickel (1995). ^[14]
• Задача наименьшей сферы может быть сформулирована как квадратичная программа ^[1], определяемая системой линейных ограничений с выпуклой квадратичной целевой функцией. Следовательно, любой алгоритм допустимого направления может дать решение задачи. ^[15] Хирн и Виджай ^[16] доказали, что подход допустимого направления, выбранный Якобсеном, эквивалентен алгоритму Кристала–Пирса.
• Двойственный к этой квадратичной программе алгоритм также может быть сформулирован явно ^[17] ; алгоритм Лоусона ^[18] может быть описан таким образом как первичный двойственный алгоритм. ^[16]
• Шамос и Хоуи ^[7] предложили алгоритм времени O( n  log  n ) для этой задачи, основанный на наблюдении, что центр наименьшего охватывающего круга должен быть вершиной самой дальней точки диаграммы Вороного входного набора точек.

Взвешенная версия задачи минимального покрывающего круга принимает в качестве входных данных набор точек в евклидовом пространстве, каждая из которых имеет вес; цель состоит в том, чтобы найти одну точку, которая минимизирует максимальное взвешенное расстояние (т. е. расстояние, умноженное на соответствующий вес) до любой точки. Исходная (невзвешенная) задача минимального покрывающего круга соответствует случаю, когда все веса равны 1. Как и в случае с невзвешенной задачей, взвешенная задача может быть решена за линейное время в любом пространстве ограниченной размерности, используя подходы, тесно связанные с алгоритмами линейного программирования ограниченной размерности, хотя в литературе снова часто встречаются более медленные алгоритмы. ^{[16] [19] [20]}

Наименьший охватывающий шар конечного множества точек изучался в римановой геометрии, включая многообразия Картана-Адамара. ^[21]

• Ограничивающая сфера
• проблема с 1 центром
• Описанная окружность
• Ближайшая строка
• Теорема Юнга

• Самый маленький код охватывающего шара Бернда Гертнера
• CGAL — пакет Min_sphere_of_spheres библиотеки алгоритмов вычислительной геометрии (CGAL)
• Miniball — реализация алгоритма с открытым исходным кодом для задачи о наименьшем объемлющем шаре для низких и умеренно высоких размерностей.