Поиск двух ближайших точек
Задача вычислительной геометрии — поиск двух ближайших точек: дано N точек в метрическом пространстве, найти пару точек с наименьшим расстоянием между ними.
Алгоритм полного перебора
Пара ближайших точек может быть вычислена за время O(N2) путём выполнения полного перебора — вычисления расстояния между всеми N(N − 1) / 2 парами точек и выбора пары с наименьшим расстоянием.
MinDist = Infinity
for i in range (1, length(P) - 1):
for j in range (i + 1, length(P)):
p = P[i]; q = P[j]
if Dist(p, q) < MinDist:
MinDist = Dist(p, q)
CloseInPoint = (p, q)
return CloseInPoint
Алгоритм «разделяй и властвуй»
Задача может быть решена за время O(N log N) с помощью рекурсивного подхода «разделяй и властвуй»:
1. Сортируем точки согласно их x-координатам.
2. Разбиваем множество точек на два подмножества равного размера вертикальной прямой.
3. Решаем задачу рекурсивно на левой и на правой частях. Это приводит к левому минимальному расстоянию DLMin и правому минимальному расстоянию DRMin, соответственно.
4. Находим минимальное расстояние DLRMin среди пар точек, из которых одна точка лежит слева от вертикальной линии, а другая точка — справа.
5. Конечным ответом будет минимальное значение среди DLMin, DRMin и DLRMin.
На четвёртом шаге пара ближайших точек не находятся на большем расстоянии, чем Dist = min( DLMin, DRMin) => для каждой точки P слева от разделяющей прямой мы должны сравнить расстояния до точек, которые лежат в прямоугольнике с размерами (Dist, 2Dist). Этот прямоугольник может содержать не более шести точек, попарное расстояние между которыми не менее DRMin => достаточно вычислить 6N расстояний. Благодаря основной теореме для рекурренции «разделяй и властвуй» получаем O(N log N).
Красная точка — точка P; Красные отрезки — растояния Dist, 2Dist.