Размещение точки для минимизации расстояния от самой дальней точки

Проверьте эту страницу. В нем описано несколько способов сделать это. http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/CG-Applets/Center/centercli.htm

_{На случай, если ссылка выше когда-нибудь исчезнет, ​​вот соответствующая часть, описывающая самый простой метод:}

Алгоритм времени O(n2)

1. Нарисуйте окружность в центре с так, чтобы точки данного множества лежали внутри окружности. Ясно, что этот круг можно уменьшить (иначе у нас есть решение).
2. Уменьшите круг, найдя точку A, наиболее удаленную от центра круга, и нарисуйте новый круг с тем же центром, проходящий через точку A. Эти два шага создают меньший окружающий круг. Причина того, что новый круг меньше, заключается в том, что этот новый круг по-прежнему содержит все точки заданного набора, за исключением того, что теперь он проходит через самую дальнюю точку x, а не охватывает ее.
3. Если окружность проходит через 2 или более точек, перейдите к шагу 4. В противном случае уменьшите окружность, переместив центр в сторону точки А, пока окружность не коснется другой точки В из набора.

4. На этом этапе мы создаем окружность C, которая проходит через две или более точек заданного множества. Если окружность содержит интервал (интервал без точек) дуги, превышающий половину окружности окружности, на которой нет точек, окружность можно уменьшить. Пусть D и E — точки на концах этого бесточечного интервала. Удерживая D и E на границе круга, уменьшайте диаметр круга, пока не будет либо случай (a), либо случай (b).

   • Case (a) The diameter is the distance DE.
     • We are done!
   • Case (b) The circle C touches another point from the set, F.
     • Check whether there exits point-free arc intervals of length more than half the circumference of C.
     • ЕСЛИ такие бесточечные дуги не выходят, ТО Готово!
   • Else
     • Goto step 4.
     • При этом три точки должны лежать на дуге длиной менее половины окружности. Повторяем шаг 4 для двух внешних из трех точек дуги.

Another page here, with a sample applet: http://www.sunshine2k.de/stuff/Java/Welzl/Welzl.html

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

Обновить

Сначала вам нужно построить диаграмму Вороного с самой дальней точкой, которая занимает время O(nlogn), и найти центр наименьшего круга среди всех вершин (если круг определяется тремя точками) и всех ребер (если круг определяется двумя точками). Общая временная сложность этого подхода составляет O(nlogn).

Я только что видел вики-страницу Задача о наименьшем круге, похоже, там есть O(n ) временной алгоритм. Вы можете проверить это, если вам небезразлична скорость, иначе не имеет значения.