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