Задача наименьшего круга - Smallest-circle problem

Несколько экземпляров наименьшего ограничивающего круга.

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

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

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

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

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

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

Позволять п - любой набор точек на плоскости, и предположим, что есть два наименьших окружающих диска п, с центрами в ${\displaystyle {\vec {z}}_{1}}$ и ${\displaystyle {\vec {z}}_{2}}$. Позволять ${\displaystyle r}$ быть их общим радиусом, и пусть ${\displaystyle 2a}$ расстояние между их центрами. С п это подмножество обоих дисков, это подмножество их пересечения. Однако их пересечение находится внутри диска с центром ${\displaystyle {\frac {1}{2}}({\vec {z}}_{1}+{\vec {z}}_{2})}$ и радиус ${\displaystyle {\sqrt {r^{2}-a^{2}}}}$, как показано на следующем изображении: С р минимально, мы должны иметь ${\displaystyle {\sqrt {r^{2}-a^{2}}}=r}$, смысл ${\displaystyle a=0}$, значит диски идентичны.[4]

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

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

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

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

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

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

Алгоритм Мегиддо^[9] основан на технике, называемой сокращением и поиском, уменьшающей размер проблемы путем удаления n / 16 ненужных точек, что приводит к повторению t (n) ≤ t (15n / 16) + cn, что дает t (n) = 16cn.

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

N / 16 баллов, которые нужно отбросить, находятся следующим образом: Очки п_я расположены в пары, что определяет n / 2 строки п_j как их биссектрисы. п_м биссектрис в порядке их направлений (ориентированных в одну полуплоскость, определяемую биссектрисой п₁) находится и строятся пары из биссектрис, такие, что в каждой паре одна биссектриса имеет направление не более п_м а другой по крайней мере п_м(направление п₁ можно рассматривать как -${\displaystyle \infty }$ или +${\displaystyle \infty }$ в соответствии с нашими потребностями.) Пусть Q_k быть пересечением биссектрис k-я пара.

Линия q в п₁ направление размещено, чтобы пройти через перекресток Q_Икс таким образом, чтобы в каждой полуплоскости, определяемой линией, было n / 8 пересечений (среднее положение). Ограниченная версия задачи с ограничениями выполняется на линии q что определяет полуплоскость, в которой расположен центр. q ' в п_м направление размещено, чтобы пройти через перекресток Q_Икс' таким образом, что в каждой половине полуплоскости, не содержащей решения, имеется n / 16 пересечений. Ограниченная версия охватывающей задачи выполняется в режиме онлайн q ' что вместе с q определяет квадрант, в котором находится центр. Мы рассматриваем точки Q_k в квадранте, не содержащемся в полуплоскости, содержащей раствор. Одна из биссектрис пары, определяющей Q_k имеет направление, определяющее, какая из точек п_я определение биссектрисы ближе к каждой точке в квадранте, содержащем центр окружности. Этот момент можно было отбросить.

Версия алгоритма с ограничениями также решается методом отсечения и поиска, но уменьшение размера проблемы путем удаления n / 4 точек, приводящих к повторению t (n) ≤ t (3n / 4) + cn, что дает t (n) = 4cn .

N / 4 отбрасываемых баллов находятся следующим образом: Очки п_я расположены в пары. Для каждого пересечения пар Q_j его биссектрисы с ограничивающей линией q (если пересечения не существует, можно сразу удалить одну точку из пары). M очков Q_j на линии q находится и в О(п) время определяется, на какой половине линии q начиная с M содержит решение ограниченной задачи. Мы рассматриваем точки Q_j от другой половины. Мы знаем, какая из точек п_я определение Q_j находится ближе к каждой точке полуоси, содержащей центр окружающего круга решения ограниченной задачи. Этот момент можно было отбросить.

Полуплоскость, в которой лежит неограниченное решение, может быть определена точками п_я на границе решения связанного круга. (Достаточно первой и последней точки на окружности в каждой полуплоскости. Если центр принадлежит их выпуклой оболочке, это решение без ограничений, в противном случае направление к ближайшему ребру определяет полуплоскость решения без ограничений.)

Алгоритм Вельцля

Алгоритм такой рекурсивный.

Первоначальный ввод - это набор п очков. Алгоритм выбирает одну точку п случайно и равномерно из п, и рекурсивно находит минимальный круг, содержащий п - { п }, т.е. все остальные точки в п Кроме п. Если возвращенный круг также включает п, это минимальный круг для всего п и возвращается.

В противном случае укажите п должен находиться на границе круга результатов. Он рекурсивен, но в качестве дополнительного параметра установлен р точек, заведомо находящихся на границе.

Рекурсия заканчивается, когда п пусто, и решение можно найти из точек в р: для 0 или 1 точки решение тривиально, для 2 точек минимальная окружность имеет центр в середине между двумя точками, а для 3 точек окружность является описанной окружностью треугольника, описываемого точками. (В трех измерениях 4 точки требуют вычисления описанной сферы тераэдра.)

Рекурсия также может завершиться, когда р имеет размер 3 (в 2D или 4 в 3D), потому что остальные точки в п должен находиться внутри круга, описанного р.

алгоритм Welzl является[8]    Вход: Конечные множества п и р точек на плоскости |р|≤ 3.    выход: Минимальный размер диска п с р на границе. если п пусто или же |р| = 3 тогда        возвращаться тривиальный (р)    выберите п в п (случайно и равномерно ) D: = welzl (п - { п }, р)    если п в D тогда        возвращаться D    возвращаться Welzl (п - { п }, р ∪ { п })

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

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

Другие алгоритмы

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

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

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

Взвешенная версия задачи о минимальном покрывающем круге принимает в качестве входных данных набор точек в евклидовом пространстве, каждая из которых имеет веса; цель состоит в том, чтобы найти единственную точку, которая минимизирует максимальное взвешенное расстояние до любой точки. Первоначальную задачу о минимальном покрывающем круге можно решить, установив для всех весов одно и то же число. Как и в случае с невзвешенной задачей, взвешенная задача может быть решена за линейное время в любом пространстве ограниченной размерности с использованием подходов, тесно связанных с алгоритмами линейного программирования с ограниченной размерностью, хотя более медленные алгоритмы снова часто встречаются в литературе.^[15][18][19]

Смотрите также

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

Рекомендации

1. Elzinga, J .; Хирн, Д. В. (1972), "Задача о минимальной покрывающей сфере", Наука управления, 19: 96–104, Дои:10.1287 / mnsc.19.1.96
2. Сильвестр, Дж. Дж. (1857 г.), «Вопрос в геометрии положения», Ежеквартальный журнал математики, 1: 79.
3. Francis, R. L .; McGinnis, L.F .; Уайт, Дж. А. (1992), Планировка и расположение объекта: аналитический подход (2-е изд.), Энглвуд Клиффс, Нью-Джерси: Prentice-Hall, Inc..
4. Вельцль 1991, п. 2.
5. Мегиддо, Нимрод (1983), "Линейные алгоритмы линейного программирования в р³ и сопутствующие проблемы », SIAM Журнал по вычислениям, 12 (4): 759–776, Дои:10.1137/0212052, МИСТЕР  0721011.
6. Матушек, Иржи; Шарир, Миха; Вельцль, Эмо (1996), «Субэкспоненциальная оценка для линейного программирования» (PDF), Алгоритмика, 16 (4–5): 498–516, CiteSeerX  10.1.1.46.5644, Дои:10.1007 / BF01940877.
7. Шамос, М.И.; Хоуи, Д. (1975), "Проблемы ближайших точек", Материалы 16-го ежегодного симпозиума IEEE по основам компьютерных наук, стр. 151–162, Дои:10.1109 / SFCS.1975.8
8. Вельцль, Эмо (1991), «Наименьшие окружающие диски (шары и эллипсоиды)», в Maurer, H. (ed.), Новые результаты и новые тенденции в компьютерных науках, Конспект лекций по информатике, 555, Springer-Verlag, стр. 359–370, CiteSeerX  10.1.1.46.1450, Дои:10.1007 / BFb0038202, ISBN  978-3-540-54869-0.
9. Мегиддо, Нимрод (1983), "Линейные алгоритмы линейного программирования в р³ и сопутствующие проблемы », SIAM Журнал по вычислениям, 12 (4): 759–776, Дои:10.1137/0212052, МИСТЕР  0721011.
10. Чакраборти, Р. К .; Чаудхури, П. К. (1981), "Замечание о геометрических решениях некоторых минимаксных задач размещения", Транспортная наука, 15 (2): 164–166, Дои:10.1287 / trsc.15.2.164.
11. Elzinga, J .; Хирн, Д. В. (1972), "Геометрические решения некоторых минимаксных задач размещения", Транспортная наука, 6 (4): 379–394, Дои:10.1287 / trsc.6.4.379.
12. Дрезнер, З .; Шелах, С. (1987), "О сложности алгоритма Эльзинга – Хирна для решения проблемы 1-центра", Математика исследования операций, 12 (2): 255–261, Дои:10.1287 / moor.12.2.255, JSTOR  3689688.
13. Hearn, D. W .; Vijay, J .; Никель, С. (1995), "Коды геометрических алгоритмов для (взвешенной) задачи о минимальном круге", Европейский журнал операционных исследований, 80: 236–237, Дои:10.1016/0377-2217(95)90075-6.
14. Якобсен, С. К. (1981), "Алгоритм для минимаксной задачи Вебера", Европейский журнал операционных исследований, 6 (2): 144–148, Дои:10.1016/0377-2217(81)90200-9.
15. Hearn, D.W .; Виджай, Дж. (1982), "Эффективные алгоритмы решения (взвешенной) задачи о минимальном круге", Исследование операций, 30 (4): 777–795, Дои:10.1287 / opre.30.4.777.
16. Elzinga, J .; Hearn, D. W .; Рэндольф, В. Д. (1976), «Минимаксное расположение многофункциональных объектов с евклидовыми расстояниями», Транспортная наука, 10 (4): 321–336, Дои:10.1287 / trsc.10.4.321.
17. Лоусон, К. Л. (1965), "Наименьший покрывающий конус или сфера", SIAM Обзор, 7 (3): 415–417, Дои:10.1137/1007084.
18. Мегиддо, Н. (1983), "Весовая проблема евклидова 1-центра", Математика исследования операций, 8 (4): 498–504, Дои:10.1287 / moor.8.4.498.
19. Мегиддо, Н.; Земель, Э. (1986), "An О(п бревноп) алгоритм рандомизации для взвешенной задачи Евклида с одним центром », Журнал алгоритмов, 7 (3): 358–368, Дои:10.1016/0196-6774(86)90027-1.

внешняя ссылка

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