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

Некоторые примеры наименьшего ограничивающего круга.

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

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

Характеристика

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

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

показывать Доказательство единственности минимального покрывающего диска.

Let P be any set of points in the plane, and suppose that there are two smallest enclosing disks of P, with centers at ${\vec {z}}_{1}$ and ${\vec {z}}_{2}$. Let $r$ be their shared radius, and let $2a$ be the distance between their centers. Since P is a subset of both disks it is a subset of their intersection. However, their intersection is contained within the disk with center ${\frac {1}{2}}({\vec {z}}_{1}+{\vec {z}}_{2})$ and radius ${\sqrt {r^{2}-a^{2}}}$, as shown in the following image: Since r is minimal, we must have ${\sqrt {r^{2}-a^{2}}}=r$, meaning $a=0$, so the disks are identical.

Решения с линейным временем

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

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

Впоследствии задача о наименьшем круге была включена в общий класс задач типа ЛП , которые можно решить с помощью алгоритмов, подобных алгоритму Вельцля, основанных на линейном программировании. Как следствие принадлежности к этому классу было показано, что зависимость от размерности постоянного множителя в $O(n)$ Ограничение по времени, которое было факториалом для метода Зейделя, можно было свести к субэкспоненциальному .

Алгоритм Мегиддо

Выполнение фазы алгоритма Мегиддо, отбрасывание из множества точек A, B, ..., U ненужных точек E, T.

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

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

The ${\textstyle {\frac {n}{16}}}$ точки, подлежащие отбрасыванию, находятся следующим образом: Точки Pi _{определяет} разбиты на пары, что ${\textstyle {\frac {n}{2}}}$ линии pj _{являются} их биссектрисами . Находят медианное среднее pm _p биссектрис в порядке их направлений (ориентированных на одну и ту же полуплоскость, определяемую биссектрисой 1 ₎ и составляют пары биссектрис так, что в каждой паре одна биссектриса имеет направление не более pm _а , другое, по крайней мере, после _{полудня} (направление p ₁ можно рассматривать как — $\infty$ или + $\infty$ в соответствии с нашими потребностями.) Пусть Q _k — пересечение биссектрис в k -й паре.

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

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

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

предоставление $t(n)=4cn$.

The ${\textstyle {\frac {n}{4}}}$ точки, подлежащие отбрасыванию, находятся следующим образом: Точки 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
    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 ⁴ ) путем проверки окружностей, определяемых всеми парами и тройками точек.

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

Взвешенные варианты задачи

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

См. также

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

Внешние ссылки

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