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

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