Такая задача построения минимальной охватывающей окружности относится к вычислительной математике и заключается в том, чтобы построить окружность минимального радиуса, охватывающую произвольное конечное множество точек 2-мерного евклидового пространства Впервые эта задача была поставлена английским математиком Джеймсом Джозефом Сильвестром в 1857 году. Смысл ее в том, чтобы найти точку, расстояние от которого до наиболее удаленной от нее точки из предложенного множества точек будет минимальным. Искомая точка – это центр минимальной охватывающей окружности, радиус окружности – расстояние до наиболее удаленной от центра точки.r2 → minmax ((xi-x)2+(yi-y)2) = r2, i=1..m, где m – количество заданных точек, xi и yi – координаты точек, r –радиус окружности, x и y – искомые координаты центра.Она распространяется не только на точки двумерного пространства, но и на пространства больших размерностей, в таких случаях она переходит в задачу построения n-мерной сферы, охватывающей все предложенные точки
Если нам дана всего одна точка, то ее можно рассматривать в качестве центра окружности с нулевым радиусом.
Если две, то в качестве центра берется середина отрезка, соединяющего обе точки, причем обе лежат на окружности. В случае большего количества точек, как минимум две точки обязаны лежать на окружности.
Задачу можно решить с помощью алгоритма линейной структуры.
Следует учесть, что окружность задается максимум тремя точками, лежащими на ней, минимальная охватывающая окружность для заданного множества точек всегда уникальна.
Алгоритмы ее поиска заключаются в подборе соответствующих окружностей заданных парами или триплетами точек и проверке принадлежности остальных точек кругам, ограниченным данными окружностями. Выполнение операций заканчивается, когда подбирается такая окружность, которая охватывает все точки.