Проблема наименьшего круга (также известный как минимальное покрытие задачи окружности , ограничивающей круг проблемы , наименьшая проблема вшита круг ) представляет собой математическую задачу вычисления наименьшего круга , который содержит все заданного набора из точек в евклидовой плоскости . Соответствующая задача в n- мерном пространстве , задача о наименьшей ограничивающей сфере , состоит в том, чтобы вычислить наименьшую n- сферу, которая содержит весь данный набор точек. [1]Задача наименьшего круга была первоначально предложена английским математиком Джеймсом Джозефом Сильвестром в 1857 г. [2]
Задача наименьшего круга на плоскости - это пример проблемы местоположения объекта ( проблема с одним центром ), в которой необходимо выбрать местоположение нового объекта для обслуживания нескольких клиентов, минимизируя самое дальнее расстояние, на которое любой клиент должен ехать, чтобы добраться до нового объекта. [3] И задача о наименьшем круге на плоскости, и задача о наименьшей ограничивающей сфере в любом многомерном пространстве ограниченной размерности разрешимы в наихудшем случае линейного времени .
Характеристика
Большинство геометрических подходов к проблеме ищут точки, лежащие на границе минимальной окружности, и основываются на следующих простых фактах:
- Минимальный круг покрытия уникален.
- Минимальная покрывающая окружность множества S может быть определена не более чем тремя точками в S, лежащими на границе окружности. Если он определяется только двумя точками, то отрезок линии, соединяющий эти две точки, должен быть диаметром минимальной окружности. Если он определяется тремя точками, то треугольник, состоящий из этих трех точек, не является тупым .
Доказательство единственности минимального накрывающего диска |
---|
Пусть P - любой набор точек на плоскости, и предположим, что есть два наименьших окружающих диска P с центрами в а также . Позволятьбыть их общим радиусом , и пустьрасстояние между их центрами. Поскольку P является подмножеством обоих дисков, это подмножество их пересечения . Однако их пересечение находится внутри диска с центром и радиус , как показано на следующем изображении: Поскольку r минимально, мы должны иметь, имея в виду , значит диски идентичны. [4] |
Решения с линейным временем
Как показал Нимрод Мегиддо [5], минимальная окружающая окружность может быть найдена за линейное время, и такая же линейная временная граница также применима к наименьшей охватывающей сфере в евклидовых пространствах любой постоянной размерности. В его статье также дается краткий обзор более ранних а также алгоритмы; [6] тем самым Мегиддо продемонстрировал, что гипотеза Шамоса и Хои - что решение задачи наименьшего круга вычислимо вв лучшем случае - было ложью. [7]
Эмо Вельцль [8] предложил простой рандомизированный алгоритм решения задачи о минимальном покрывающем круге, которая выполняется за ожидаемое время. , основанный на алгоритме линейного программирования Раймунда Зайделя .
Впоследствии задача наименьшего круга была включена в общий класс задач типа LP, которые могут быть решены с помощью алгоритмов, подобных алгоритму Вельцля, основанному на линейном программировании. Вследствие принадлежности к этому классу было показано, что зависимость от размерности постоянного множителя ввременная граница, которая была факториальной для метода Зейделя, могла быть уменьшена до субэкспоненциальной . [6]
Алгоритм Мегиддо
Алгоритм Мегиддо [9] основан на технике, называемой сокращением и поиском, уменьшающей размер проблемы за счет удаленияненужные моменты. Это приводит к повторению давая .
Алгоритм достаточно сложен, что отражается в его большой мультипликативной константе. При редукции необходимо дважды решить аналогичную задачу, в которой центр искомого ограничивающего круга должен лежать на заданной линии . Решение подзадачи - это либо решение неограниченной задачи, либо оно используется для определения полуплоскости, в которой расположен центр неограниченного решения.
В отбрасываемые точки находятся следующим образом: точки P i объединяются в пары, что определяетпрямые p j их биссектрисы . Находится среднее значение p m биссектрис в порядке их направлений (ориентированных на одну и ту же полуплоскость, определяемую биссектрисой p 1 ), и строятся пары биссектрис, так что в каждой паре одна биссектриса имеет направление не более p m, а другие по крайней мере p m (направление p 1 можно рассматривать как - или +в соответствии с нашими потребностями.) Пусть Q k будет пересечением биссектрис в k -й паре.
Прямая q в направлении p 1 проходит через пересечение Q x такое, что естьпересечения в каждой полуплоскости, определяемой линией (срединное положение). Ограниченная версия задачи охвата выполняется на прямой q ', которая определяет полуплоскость, в которой расположен центр. Прямая q 'в направлении p m проходит через пересечение Q x', такое что естьпересечения в каждой половине полуплоскости, не содержащей решения. Ограниченная версия задачи включения выполняется в строке q ', которая вместе с q определяет квадрант, в котором расположен центр. Рассмотрим точки Q k квадранта, не лежащие в полуплоскости, содержащей решение. Одна из биссектрис пары, определяющей Q k, имеет направление, гарантирующее, какая из точек P i, определяющих биссектрису, находится ближе к каждой точке в квадранте, содержащем центр окружности. Этот момент можно было отбросить.
Ограниченная версия алгоритма также решается с помощью техники сокращения и поиска, но уменьшение размера проблемы путем удаления точки, ведущие к повторению
давая .
В отбрасываемые точки находятся следующим образом: точки P i объединяются в пары. Для каждой пары находится пересечение Q j ее биссектрисы с линией ограничения q (если это пересечение не существует, мы могли бы немедленно удалить одну точку из пары). Находится медиана M точек Q j на прямой q и за время O ( n ) определяется, какая половина линии q, начинающаяся в M, содержит решение задачи с ограничениями. Рассмотрим точки Q j из другой половины. Мы знаем, какая из точек P i, определяющих Q j, находится ближе к каждой точке полуоси, содержащей центр окружающего круга решения задачи с ограничениями. Этот момент можно было отбросить.
Полуплоскость, в которой лежит неограниченное решение, может быть определена точками P i на границе решения в виде ограниченного круга. (Достаточно первой и последней точки на окружности в каждой полуплоскости. Если центр принадлежит их выпуклой оболочке , это решение без ограничений, в противном случае направление на ближайший край определяет полуплоскость решения без ограничений.)
Алгоритм Вельцля
Алгоритм рекурсивный .
Первоначальный ввод - это набор P точек. Алгоритм выбирает одну точку p случайным образом и равномерно из P и рекурсивно находит минимальную окружность, содержащую P - { p }, то есть все другие точки в P, кроме p . Если возвращаемый круг также включает p , это минимальный круг для всей P и возвращается.
В противном случае точка p должна лежать на границе результирующего круга. Он рекурсивен, но с набором R точек, которые, как известно, находятся на границе, в качестве дополнительного параметра.
Рекурсии завершается , когда Р является пустым , и решение может быть найдено из точек в R : 0 или 1 точек решение тривиально, 2 очка минимальный круг имеет свой центр в средней точке между двумя точками, и 3 точек окружность - это описанная окружность треугольника, описываемого точками. (В трех измерениях, 4 балла требует расчета circumsphere о наличии тетраэдра .)
Рекурсия может также прекратить , когда R имеет размер 3 (в 2D или 4 в 3D) , так как остальные точки в Р должны лежать в пределах окружности , описываемой R .
алгоритм welzl является [8] входными данными : Конечные множества P и R точек на плоскости | R | ≤ 3. Выход: минимальный диск, содержащий P с R на границе. если P пусто или | R | = 3, затем вернуть trivial ( R ) выбрать p в P ( случайно и равномерно ) D: = welzl ( Р - { р }, R ) , если р находится в D , то возвращают D return welzl ( P - { p }, R ∪ { p })
В статье Велцля говорится, что достаточно случайным образом переставить входные данные в начале, а не выполнять независимый случайный выбор p для каждой рекурсии.
В нем также говорится, что производительность улучшается за счет динамического изменения порядка точек, так что те, которые оказываются вне круга, впоследствии рассматриваются ранее, но это требует изменения в структуре алгоритма, чтобы сохранить P как «глобальный».
Другие алгоритмы
До того, как результат Мегиддо показал, что задача наименьшего круга может быть решена за линейное время, в литературе появилось несколько алгоритмов более высокой сложности. Наивный алгоритм решает проблему за время O ( n 4 ), проверяя круги, определенные всеми парами и тройками точек.
- Алгоритм Кристалла и Пирса применяет стратегию локальной оптимизации , которая поддерживает две точки на границе окружающего круга и многократно сжимает круг, заменяя пару граничных точек, пока не будет найден оптимальный круг. Чакраборти и Чаудхури [10] предлагают метод линейного времени для выбора подходящей начальной окружности и пары граничных точек на этой окружности. Каждый шаг алгоритма включает в себя в качестве одной из двух граничных точек новую вершину выпуклой оболочки , поэтому, если оболочка имеет h вершин, этот метод может быть реализован для выполнения за время O ( nh ).
- Эльзинга и Хирн [11] описали алгоритм, который поддерживает покрывающую окружность для подмножества точек. На каждом шаге точка, не покрытая текущей сферой, используется для поиска большей сферы, которая покрывает новое подмножество точек, включая найденную точку. Хотя в худшем случае время работы составляет O ( h 3 n ), авторы сообщают, что в их экспериментах он работал за линейное время. Сложность метода была проанализирована Дрезнером и Шелахом. [12] И коды Fortran, и C доступны от Hearn, Vijay & Nickel (1995) . [13]
- Задачу наименьшей сферы можно сформулировать как квадратичную программу [1], определяемую системой линейных ограничений с выпуклой квадратичной целевой функцией. Следовательно, любой допустимый алгоритм направления может дать решение проблемы. [14] Хирн и Виджай [15] доказали, что подход допустимого направления, выбранный Якобсеном, эквивалентен алгоритму Кристал-Пирса.
- Двойственная к этой квадратичной программе также может быть сформулирована явно; [16] алгоритм Лоусона [17] может быть описан таким образом как первичный двойственный алгоритм. [15]
- Шамос и Хои [7] предложили алгоритм времени O ( n log n ) для задачи, основанный на наблюдении, что центр наименьшего окружающего круга должен быть вершиной самой дальней точки диаграммы Вороного входного набора точек.
Взвешенные варианты задачи
Взвешенная версия задачи о минимальном покрывающем круге принимает в качестве входных данных набор точек в евклидовом пространстве, каждая из которых имеет веса; цель состоит в том, чтобы найти единственную точку, которая минимизирует максимальное взвешенное расстояние до любой точки. Первоначальную задачу о минимальном покрывающем круге можно решить, установив для всех весов одно и то же число. Как и в случае с невзвешенной задачей, взвешенная задача может быть решена за линейное время в любом пространстве ограниченной размерности с использованием подходов, тесно связанных с алгоритмами линейного программирования с ограниченной размерностью, хотя более медленные алгоритмы снова часто встречаются в литературе. [15] [18] [19]
Смотрите также
- Ограничивающая сфера
- 1-центровая проблема
- Описанный круг
- Ближайшая строка
- Теорема Юнга
Рекомендации
- ^ a b Elzinga, J .; Херн, DW (1972), "Минимальное покрытие проблемы сферы", Управление науки , 19 : 96-104, DOI : 10,1287 / mnsc.19.1.96
- ^ Сильвестр, Дж. Дж. (1857), "Вопрос о геометрии ситуации", Quarterly Journal of Mathematics , 1 : 79.
- ^ Фрэнсис, Р.Л .; Макгиннис, LF; Уайт, Дж. А. (1992), Планировка и расположение объекта: аналитический подход (2-е изд.), Englewood Cliffs, NJ: Prentice-Hall, Inc..
- ^ Welzl 1991 , стр. 2.
- ^ Мегиддо, Нимрод (1983), "алгоритмы линейного времени для линейного программирования в R 3 и связанные с этим проблемы", SIAM журнал по вычислениям , 12 (4): 759-776, DOI : 10,1137 / 0212052 , МР 0721011.
- ^ а б Матушек, Иржи ; Шарир, Миха ; Welzl, Эмо (1996), "субэкспоненциальной граница для линейного программирования" (PDF) , Algorithmica , 16 (4-5): 498-516, CiteSeerX 10.1.1.46.5644 , DOI : 10.1007 / BF01940877.
- ^ а б Шамос, Мичиган ; Хоя, D. (1975), "Ближайшие проблемы точки", Труды 16 - го ежегодного симпозиума IEEE по Основы информатики , С. 151-162,. DOI : 10.1109 / SFCS.1975.8
- ^ а б Welzl, Emo (1991), «Наименьшие окружающие диски (шары и эллипсоиды)», в Maurer, H. (ed.), New Results and New Trends in Computer Science , Lecture Notes in Computer Science, 555 , Springer-Verlag, pp. . 359-370, CiteSeerX 10.1.1.46.1450 , DOI : 10.1007 / BFb0038202 , ISBN 978-3-540-54869-0.
- ^ Мегиддо, Нимрод (1983), "алгоритмы линейного времени для линейного программирования в R 3 и связанные с этим проблемы", SIAM журнал по вычислениям , 12 (4): 759-776, DOI : 10,1137 / 0212052 , МР 0721011.
- ^ Чакраборти, РК; Чоудхури, П. К. (1981), "Замечание о геометрических решений для некоторых минимаксных задач размещения", транспорт Наука , 15 (2): 164-166, DOI : 10,1287 / trsc.15.2.164.
- ^ Elzinga, J .; Херн, DW (1972), "Геометрические решения некоторых минимаксимальных задач размещения", транспорт Наука , 6 (4): 379-394, DOI : 10,1287 / trsc.6.4.379.
- ^ Дрезнер, З .; Шел, С. (1987), "О сложности алгоритма Элзинга-Херне для задачи 1-центра", Математика исследования операций , 12 (2): 255-261, DOI : 10.1287 / moor.12.2.255 , JSTOR 3689688.
- ^ Хирн, DW; Vijay, J .; Никель, С. (1995), «Коды геометрических алгоритмов для (взвешенной) задачи о минимальном круге», European Journal of Operational Research , 80 : 236–237, DOI : 10.1016 / 0377-2217 (95) 90075-6.
- ^ Jacobsen, SK (1981), "Алгоритм для задачи минимакса Weber", Европейский журнал оперативных исследований , 6 (2): 144-148, DOI : 10,1016 / 0377-2217 (81) 90200-9.
- ^ а б в Хирн, DW; Виджи, J. (1982), "Эффективные алгоритмы (взвешенная) минимальная окружность задачи", исследование операций , 30 (4): 777-795, DOI : 10,1287 / opre.30.4.777.
- ^ Elzinga, J .; Хирн, DW; Randolph, WD (1976), "Минимакс multifacility место с евклидовых расстояний", транспорт Наука , 10 (4): 321-336, DOI : 10,1287 / trsc.10.4.321.
- ^ Lawson, 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), "О О ( п войти п ) рандомизации алгоритм взвешенного евклидова задачи 1-центр", журнал алгоритмов , 7 (3): 358-368, DOI : 10.1016 / 0196-6774 (86 ) 90027-1.
Внешние ссылки
- Наименьший код закрывающего шара Бернда Гертнера
- CGAL Min_sphere_of_spheres пакет в вычислительной геометрии алгоритмов библиотеки (CGAL)
- Miniball - реализация алгоритма с открытым исходным кодом для решения задачи наименьшего вмещающего шара для малых и умеренно больших размеров.