Поиск пары ближайших точек за $O(n)$
Решим за линейное время следующую задачу:
Задача: Даны $n$ точек на плоскости. Требуется найти такую пару точек, что расстояние между ними минимально среди всех расстояний между всеми парами данных точек.
У этой задачи есть детерминированный алгоритм, основанный на идее «разделяй и властвуй», работающий за $O(n \log n)$. Мы же рассмотрим рандомизированный алгоритм, работающий за ожидаемое время $O(n)$.
Давайте будем постепенно добавлять точки по одной в случайном порядке, поддерживая пару ближайших точек. Пусть на данный момент уже было добавлено сколько-то точек, и текущее минимальное расстояние равно $d$. Побьем всю плоскость на квадраты $d \times d$ и для каждого квадрата в хеш-таблице будем хранить все точки, находящиеся в этом квадрате. При этом можно заметить, что так как на данный момент минимальное расстояние между точками равно $d$, то расстояние между любой парой точек не меньше $d$, поэтому в каждом квадрате не больше $4$ точек.
Заметим, что если мы добавляем какую-то новую точку, то если минимальное расстояние изменилось, то есть какая-то точка, которая находится на расстоянии меньше $d$ от новой точки. При этом обратим внимание на то, что эта точка должна находиться либо в том же квадрате $d \times d$, либо в соседнем (по стороне или диагонали), ведь если нарисовать круг радиуса $d$ с центром в новой точке, он целиком будет лежать в квадрате $3d \times 3d$, в центральном квадрате которого лежит новая точка.
Так как в каждом квадрате лежит не больше $4$ точек, нам придется перебрать не более $9 \cdot 4 = 36$ точек в поиске пары для новой точки. То есть добавление новой точки будет происходить за константное время. Однако если мы все таки нашли новую пару, то нам придется перестроить всю структуру квадратов, потому что $d$ уменьшится.
Кажется, что такой алгоритм будет работать за квадратичное время, однако вспомним, что мы добавляем точки в случайном порядке! Заметим, что если мы перестроили структуру после добавления $k$-й точки, то это одна из двух точек в паре самых близких. Так как эта точка была выбрана случайно, то вероятность такого события — $\frac{2}{k}$ (если есть несколько одинаковых минимальных расстояний, то либо до добавления этой точки расстояние уже было таким, и ничего перестраивать не надо, либо же во всех таких минимальных расстояниях одной из точек является наша новая точка, и тогда вероятность еще меньше — $\frac{1}{k}$). Если это событие произошло, то нам нужно перестроить заново структуру. Это происходит за $O(k)$. Поэтому ожидаемое время работы равно $\sum_{k = 1}^{n} \frac{2}{k} \cdot k = \sum_{k = 1}^{n} 2 = 2n = O(n)$. Что и требовалось доказать.
Замечание: Если координаты точек целые, то в алгоритме можно обойтись без вещественных чисел. Вместо минимального расстояния будем хранить его квадрат, а делить на квадраты будем со стороной не $d$, а $\left\lfloor d \right\rfloor$. Очевидно, от этого асимптотика не поменяется.
Замечание: Чтобы получить номер квадрата, в котором находится точка, вы скорее всего будете делить его координаты на $d$. Будьте внимательны, что если в множестве есть совпадающие точки, то $d$ может стать равно нулю. В этом случае нужно сразу завершиться, потому что более близких точек точно уже не будет.
С реализацией можно ознакомиться по ссылке.
Замечание: Легко обобщить этот алгоритм для бóльших размерностей. Нужно побить пространство на кубы со стороной $d$ и искать пару для новой точки во всех соседних кубах. Для фиксированной размерности алгоритм будет все еще линейным.