Задача о наименьшей окружности

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

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

ОписаниеПравить

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

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

Решение за линейное времяПравить

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

Эмо Вельцль^[5] предложил простой рандомизированный алгоритм для задачи покрытия кругом, среднее время работы которого равно $\text{[math]}$ $\text{[math]}$ $O(N)$ , основанный на алгоритме линейного программирования Раймунда Зейделя. Алгоритм является рекурсивным и в качестве аргументов принимает два множества точек S и Q. Алгоритм вычисляет наименьшую окружность, ограничивающую объединение множеств S и Q, если любая точка множества Q является граничной точкой возможной ограничивающей окружности. Исходная задача о наименьшей ограничивающей окружности может быть решена, начав с S, равного полному множеству точек, и с Q, равного пустому множеству. Когда алгоритм вызывает себя рекурсивно, он увеличивает множество Q, пока в него не попадут все граничные точки.

Алгоритм обрабатывает точки множества S в случайном порядке, используя множество P обработанных точек и минимальную окружность, ограничивающую объединение P и Q. На каждом шаге алгоритм проверяет, принадлежит ли обрабатываемая точка r этой окружности. Если не принадлежит, алгоритм заменяет ограничивающую окружность путём рекурсивного вызова алгоритма на множествах P и Q+r. В зависимости о того, заменяется ли окружность или нет, r включается в множество P. Обработка каждой точки, таким образом, заключается в проверке (за постоянное время), принадлежит ли точка окружности, и возможном рекурсивном вызове алгоритма. Можно показать, что i-я обрабатываемая точка имеет вероятность $\text{[math]}$ $\text{[math]}$ $O(1/i)$ рекурсивного вызова, а потому общее время линейно.

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

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

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

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

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

Взвешенная версия задачи о минимальном накрывающем круге берёт в качестве входных данных точки евклидова пространства с назначенным каждой точке весом. Целью задачи является поиск одной точки, минимизирующей максимальное взвешенное расстояние до любой точки. Исходную задачу покрытия кругом можно рассматривать как задачу с одинаковыми весами. Как и в случае задачи без весов, взвешенную задачу можно решить за линейное время в любом пространстве ограниченной размерности, если использовать подход, основанный на алгоритме линейного программирования ограниченной размерности, хотя в литературе постоянно встречаются более медленные алгоритмы^[12]^[16]^[17].

См. такжеПравить

ПримечанияПравить

↑ ¹ ² Elzinga, Hearn, 1972, с. 96–104.
↑ Sylvester, 1857, с. 79.
↑ Francis, McGinnis, White, 1992.
↑ Megiddo, 1983, с. 759–776.
↑ Welzl, 1991, с. 359–370.
↑ Matoušek, Sharir, Welzl, 1996, с. 498–516.
↑ Chakraborty, Chaudhuri, 1981, с. 164–166.
↑ Elzinga, Hearn, 1972, с. 379–394.
↑ Drezner, Shelah, 1987, с. 255–261.
↑ Hearn, Vijay, Nickel, 1995, с. 236–237.
↑ Jacobsen, 1981, с. 144–148.
↑ ¹ ² ³ Hearn, Vijay, 1982, с. 777–795.
↑ Elzinga, Hearn, Randolph, 1976, с. 321–336.
↑ Lawson, 1965, с. 415–417.
↑ Shamos, Hoey, 1975, с. 151–162.
↑ Megiddo, 1983, с. 498–504.
↑ Megiddo, Zemel, 1986, с. 358–368.

ЛитератураПравить

J. Elzinga, D. W. Hearn. The minimum covering sphere problem // Management Science. — 1972. — Т. 19. — doi:10.1287/mnsc.19.1.96.
J. J. Sylvester. A question in the geometry of situation // Quarterly Journal of Mathematics. — 1857. — Т. 1. — С. 79.
R. L. Francis, L. F. McGinnis, J. A. White. Facility Layout and Location: An Analytical Approach. — 2nd. — Englewood Cliffs, N.J.: Prentice–Hall, Inc., 1992.
Nimrod Megiddo. Linear-time algorithms for linear programming in $\text{[math]}$ R³ and related problems // SIAM Journal on Computing. — 1983. — Т. 12, вып. 4. — С. 759–776. — doi:10.1137/0212052.
Emo Welzl. New Results and New Trends in Computer Science / H. Maurer. — Springer-Verlag, 1991. — Т. 555. — С. 359–370. — (Lecture Notes in Computer Science). — doi:10.1007/BFb0038202.
Jiří Matoušek, Micha Sharir, Emo Welzl. A subexponential bound for linear programming // Algorithmica. — 1996. — Т. 16. — С. 498–516. — doi:10.1007/BF01940877.
R. K. Chakraborty, P. K. Chaudhuri. Note on geometrical solutions for some minimax location problems // Transportation Science. — 1981. — Т. 15. — doi:10.1287/trsc.15.2.164.
J. Elzinga, D. W. Hearn. Geometrical solutions for some minimax location problems // Transportation Science. — 1972. — Т. 6. — С. 379–394. — doi:10.1287/trsc.6.4.379.
Z. Drezner, S. Shelah. On the complexity of the Elzinga–Hearn algorithm for the 1-center problem // Mathematics of Operations Research. — 1987. — Т. 12, вып. 2. — С. 255–261. — doi:10.1287/moor.12.2.255. — JSTOR 3689688.
D. W. Hearn, J. Vijay, S. Nickel. Codes of geometrical algorithms for the (weighted) minimum circle problem // European Journal of Operational Research. — 1995. — Т. 80. — doi:10.1016/0377-2217(95)90075-6.
S. K. Jacobsen. An algorithm for the minimax Weber problem // European Journal of Operational Research. — 1981. — Т. 6. — doi:10.1016/0377-2217(81)90200-9.
D. W. Hearn, J. Vijay. Efficient algorithms for the (weighted) minimum circle problem // Operations Research. — 1982. — Т. 30, вып. 4. — doi:10.1287/opre.30.4.777.
J. Elzinga, D. W. Hearn, W. D. Randolph. Minimax multifacility location with Euclidean distances // Transportation Science. — 1976. — Т. 10. — doi:10.1287/trsc.10.4.321.
C. L. Lawson. The smallest covering cone or sphere // SIAM Review. — 1965. — Т. 7, вып. 3. — doi:10.1137/1007084.
M. I. Shamos, D. Hoey. Proceedings of 16th Annual IEEE Symposium on Foundations of Computer Science. — 1975. — doi:10.1109/SFCS.1975.8.
N. Megiddo. The weighted Euclidean 1-center problem // Mathematics of Operations Research. — 1983. — Т. 8. — doi:10.1287/moor.8.4.498.
N. Megiddo, E. Zemel. An O(n log n) randomizing algorithm for the weighted Euclidean 1-center problem // Journal of Algorithms. — 1986. — Т. 7. — doi:10.1016/0196-6774(86)90027-1.

СсылкиПравить

Bernd Gärtner's smallest enclosing ball code
CGAL the Min_sphere_of_spheres package of the Computational Geometry Algorithms Library (CGAL)
Miniball an open-source implementation of an algorithm for the smallest enclosing ball problem for low and moderately high dimensions

[_56b0c6ad49050e53-1] ¹ ² Elzinga, Hearn, 1972, с. 96–104.

[_3f59318559b2fe75-2] Sylvester, 1857, с. 79.

[_4b3282096dfbe61f-3] Francis, McGinnis, White, 1992.

[_71f366f6fc5642f1-4] Megiddo, 1983, с. 759–776.

[_e1a50b320caa959f-5] Welzl, 1991, с. 359–370.

[_f2d22546a87043b7-6] Matoušek, Sharir, Welzl, 1996, с. 498–516.

[_3ad455b8efec3bea-7] Chakraborty, Chaudhuri, 1981, с. 164–166.

[_3d7698934e7aab58-8] Elzinga, Hearn, 1972, с. 379–394.

[_8bd3f28e52f37d97-9] Drezner, Shelah, 1987, с. 255–261.

[_de07f0a3c2255044-10] Hearn, Vijay, Nickel, 1995, с. 236–237.

[_8cb88ddaae865e44-11] Jacobsen, 1981, с. 144–148.

[_e2d40bd47bbfd467-12] ¹ ² ³ Hearn, Vijay, 1982, с. 777–795.

[_65427132f045e587-13] Elzinga, Hearn, Randolph, 1976, с. 321–336.

[_6155cb9e18fa270d-14] Lawson, 1965, с. 415–417.

[_2945cbd5602c9218-15] Shamos, Hoey, 1975, с. 151–162.

[_a76dc10ba50f119a-16] Megiddo, 1983, с. 498–504.

[_709597496dbcddc5-17] Megiddo, Zemel, 1986, с. 358–368.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]