Построение

охватывающей

окружности

Пример

Задача

Требуется найти окружность с минимальным радиусом, содержащую заданные точки.

Шаг 1

Шаг 2

Шаг 3

Выбрать любую точку и построить на отрезке между ней и самой дальней точке окружность, как на диаметре

Взять точку, наиболее удалённую от центра текущей окружности и построить новую окружность на отрезке между ней и наиболее удалённой от неё точкой на границе старой окружности. Если окружность не включает все точки на границе старой окружности, построить новую окружность по трём точкам - на границе старой окружности и новой

Повторять, пока все точки не окажутся внутри

Информация об алгоритме

Сложность : O(n²).

Тип: динамическое программирование (разбиение на задачи по добавлению точки)

Тема: вычислительная геометрия