Минимальная покрывающая окружность $O(n)$



Решим за линейное время следующую задачу:

Задача: Даны $n$ точек на плоскости. Требуется найти окружность минимального радиуса, такую что все данные точки лежат внутри или на границе этой окружности.

В отличие от других рассмотренных рандомизированных геометрических алгоритмов, у которых есть общеизвестные детерминированные аналоги, работающие в $\log n$ раз дольше, в данном случае рандомизированное решение будет единственным применимым с практической точки зрения.

Есть два варианта того, как будет выглядеть минимальная покрывающая окружность: либо это описанная окружность какой-то тройки из данных точек, либо окружность, построенная на отрезке между двумя какими-то точками как на диаметре, потому что во всех других случаях ее радиус можно немного уменьшить так, чтобы эта окружность все еще содержала в себе все данные точки.

test

Давайте по очереди добавлять точки в случайном порядке, поддерживая минимальную покрывающую окружность текущего набора точек. Если новая точка лежит внутри текущей окружности, то ничего менять не надо, а в противном случае нужно перестроить окружность. Стоит заметить, что если новая точка не лежит в старой окружности, то она обязана лежать на новой минимальной окружности. На окружности лежит $3$ точки, поэтому вероятность такого события — $\frac{3}{k}$, где $k$ — индекс новой точки (если на окружности лежит больше $3$ точек, то эта окружность была минимальной еще до добавления текущей точки, а если окружность построена на двух точках как на диаметре, то вероятность еще меньше — $\frac{2}{k}$). Теперь если мы построим линейный алгоритм, который находит минимальную покрывающую окружность, проходящую через новую точку, то итоговая асимптотика алгоритма будет $\sum_{k = 1}^{n} \frac{3}{k} \cdot k = \sum_{k = 1}^{n} 3 = 3n = O(n)$.

test

Алгоритм нахождения минимальной покрывающей окружности, проходящей через новую точку аналогичен алгоритму, который мы только что рассмотрели. Мы перебираем все остальные точки в случайном порядке, и если новая точка лежит вне текущей окружности, то эту окружность нужно перестроить. Вероятность того, что новая точка лежит на минимальной окружности не больше $\frac{2}{k}$, поэтому алгоритм будет линейным.

Остается последний этап: зафиксированы уже две точки и нужно построить минимальную покрывающую окружность, проходящую через них. Алгоритм аналогичен. Начинаем с окружности, построенной на отрезке между этими двумя точками как на диаметре, а затем добавляем остальные точки в случайном порядке. Вероятность, что окружность нужно перестроить не больше $\frac{1}{k}$, при этом если зафиксированы уже три точки на окружности, то окружность определяется однозначно.