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

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

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

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

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

Поскольку r минимально, мы должны иметь , то есть , поэтому диски идентичны. ^[4]${\ Displaystyle {\ sqrt {г ^ {2} -а ^ {2}}} = г}$${\ Displaystyle а = 0}$

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

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