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