Ближайшая пара точек: разделяй и властвуй за O(n log n) и sweep line

Задача о ближайшей паре точек: от перебора за O(n²) к «разделяй и властвуй» за O(n log n), почему в полосе хватает 7 соседей, решение заметающей прямой и K Closest Points to Origin.

14 мин чтенияалгоритмы · геометрия · разделяй и властвуй · python

Коротко

ЧтоСуть
ЗадачаДаны nn точек на плоскости, найти минимальное расстояние между двумя из них
ПереборВсе пары, O(n2)O(n^2) — честно, но на 10510^5 точек это 5⋅1095 \cdot 10^9 сравнений
Разделяй и властвуйРежем по медиане xx, решаем половины, склеиваем через узкую полосу — O(nlog⁡n)O(n \log n)
Главный трюкВ полосе каждую точку достаточно сравнить максимум с 7 следующими по yy
Sweep lineИдём слева направо, держим окно точек шириной dd, упорядоченное по yy — тоже O(nlog⁡n)O(n \log n)
Родственная задачаK Closest Points to Origin — не про пары, а про top-k: куча O(nlog⁡k)O(n \log k) или quickselect O(n)O(n)

Ближайшая пара точек — классика из учебников (она есть в CLRS в главе про вычислительную геометрию) и любимый пример «разделяй и властвуй», где самое интересное происходит не в рекурсии, а на этапе склейки. На собеседованиях её саму дают нечасто, зато вопрос «почему там именно 7?» любят задавать, чтобы проверить, понимаете ли вы доказательства, а не только заучили код. А вот K Closest Points to Origin (LeetCode 973) встречается постоянно — разберём и её, потому что их часто путают.

Постановка задачи

На входе — список точек (xi,yi)(x_i, y_i), n≥2n \ge 2. Нужно найти

min⁡i<j(xi−xj)2+(yi−yj)2.\min_{i < j} \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}.

Точки могут совпадать — тогда ответ 00. Координаты могут быть дробными. Иногда просят вернуть саму пару, а не расстояние; это меняет код на пару строк.

Пример: для точек (2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4) ответ — 2≈1.414\sqrt{2} \approx 1.414, пара (2, 3) и (3, 4).

Наивное решение: все пары

import math def brute_force(points): best = math.inf n = len(points) for i in range(n): for j in range(i + 1, n): best = min(best, math.dist(points[i], points[j])) return best

n(n−1)2\frac{n(n-1)}{2} пар, O(n2)O(n^2) времени, O(1)O(1) памяти. Для n≤3000n \le 3000 этого хватает, и на собеседовании это правильный первый шаг: назовите его, оцените и переходите к улучшению. Ещё он пригодится как эталон для стресс-тестов — без него ошибку в оптимальной версии почти не найти.

Интуиция: что даёт сортировка

В одномерном случае задача тривиальна: отсортируй числа, и ближайшая пара обязательно окажется соседней. O(nlog⁡n)O(n \log n).

На плоскости так не работает. Точки, соседние по xx, могут быть далеко по yy, а настоящая ближайшая пара — разнесена в отсортированном по xx массиве на сотни позиций. Сортировка по одной координате не спасает, но подсказывает идею: если разрезать множество вертикальной прямой, то пары делятся на три вида — обе точки слева, обе справа и «через разрез». Первые два вида — та же задача меньшего размера. Весь вопрос в третьем.

Разделяй и властвуй

Схема

  1. Сортируем точки по xx один раз в начале.
  2. Делим массив пополам по индексу. Пусть mid_x — координата xx средней точки, это вертикальная прямая разреза.
  3. Рекурсивно находим dLd_L — ответ для левой половины и dRd_R — для правой. Пусть d=min⁡(dL,dR)d = \min(d_L, d_R).
  4. Ищем пары «через разрез», которые ближе dd. Если нашли — обновляем dd.

Шаг 4 и есть вся магия. Наивно он стоит n2⋅n2\frac{n}{2} \cdot \frac{n}{2}, и тогда рекурсия даёт те же O(n2)O(n^2). Надо сделать его линейным.

Полоса шириной 2d

Первое наблюдение: если пара «через разрез» ближе dd, то обе её точки лежат не дальше dd от прямой разреза по горизонтали. Иначе одна только разница по xx уже больше dd. Значит, рассматривать можно только точки из полосы ∣x−mid_x∣<d|x - \text{mid\_x}| < d.

Но этого мало: в полосу могут попасть вообще все точки — например, если они выстроены вдоль вертикальной линии. Нужно второе наблюдение.

Второе наблюдение: упорядочим точки полосы по yy. Для точки pp интересны только те, у которых yy больше на величину меньше dd (пары «вниз» мы уже проверили, когда смотрели с другой точки). И таких точек мало — не больше 7.

Почему в полосе достаточно 7 соседей

Это то место, которое стоит уметь объяснить на доске.

Возьмём точку pp из полосы. Все интересные для неё точки лежат в прямоугольнике шириной 2d2d (вся полоса) и высотой dd (от ypy_p до yp+dy_p + d). Разрежем этот прямоугольник на 8 квадратов со стороной d/2d/2: 4 слева от разреза и 4 справа.

mid_x | +----+----+----+----+ y_p + d | | | | | +----+----+----+----+ | | | | | +----+----+----+----+ y_p <-------- 2d ------->

Каждый маленький квадрат целиком лежит в одной половине. Его диагональ равна d2<d\frac{d}{\sqrt{2}} < d. Значит, в нём не может быть двух точек из одной половины: иначе расстояние между ними было бы меньше dd, а мы знаем, что внутри каждой половины все пары не ближе dd (это и есть dLd_L и dRd_R). Итого в прямоугольнике не больше 8 точек, одна из которых — сама pp. Остаётся максимум 7 кандидатов.

Отсюда и правило в коде: для каждой точки полосы смотрим не дальше 7 следующих по yy. Константа не обязана быть точной — в разных учебниках встречаются 5, 6, 7 и даже 15, в зависимости от того, насколько аккуратно оценивают. Важно, что она не зависит от nn, и проход по полосе становится линейным.

На практике удобнее не считать до 7, а прерывать внутренний цикл, как только разница по yy достигла dd: дальше точки только выше. Это работает и без явного лимита, а оценка выше гарантирует, что цикл короткий.

Откуда берётся O(n log n), а не O(n log² n)

Если на каждом уровне рекурсии сортировать полосу по yy заново, склейка стоит O(nlog⁡n)O(n \log n), и общее время получается

T(n)=2T(n/2)+O(nlog⁡n)=O(nlog⁡2n).T(n) = 2T(n/2) + O(n \log n) = O(n \log^2 n).

Это уже хорошо, но не оптимально. Трюк — тот же, что в сортировке слиянием: пусть рекурсия возвращает не только ответ, но и свои точки, отсортированные по yy. Тогда на уровне выше эти два списка сливаются за O(n)O(n), и

T(n)=2T(n/2)+O(n)=O(nlog⁡n).T(n) = 2T(n/2) + O(n) = O(n \log n).

По сути, мы одновременно сортируем точки по yy слиянием и решаем исходную задачу.

Код

import math def closest_pair(points): px = sorted(points) # по x (при равенстве — по y) def solve(lo, hi): # Возвращает (минимальное расстояние, точки [lo, hi) отсортированные по y) if hi - lo <= 3: best = math.inf for i in range(lo, hi): for j in range(i + 1, hi): best = min(best, math.dist(px[i], px[j])) return best, sorted(px[lo:hi], key=lambda p: p[1]) mid = (lo + hi) // 2 mid_x = px[mid][0] d_left, left = solve(lo, mid) d_right, right = solve(mid, hi) d = min(d_left, d_right) # Слияние двух списков по y, как в merge sort by_y = [] i = j = 0 while i < len(left) and j < len(right): if left[i][1] <= right[j][1]: by_y.append(left[i]) i += 1 else: by_y.append(right[j]) j += 1 by_y.extend(left[i:]) by_y.extend(right[j:]) # Полоса шириной 2d вокруг разреза, уже упорядоченная по y strip = [p for p in by_y if abs(p[0] - mid_x) < d] for i in range(len(strip)): for j in range(i + 1, min(i + 8, len(strip))): if strip[j][1] - strip[i][1] >= d: break d = min(d, math.dist(strip[i], strip[j])) return d, by_y return solve(0, len(px))[0] pts = [(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)] print(closest_pair(pts)) # 1.4142135623730951

Пара деталей:

  • База рекурсии — 2 или 3 точки, их проще перебрать. Если сделать базу «одна точка», придётся обрабатывать d=∞d = \infty в полосе и аккуратнее делить.
  • Делим по индексу, а не по значению mid_x. Если много точек с одинаковым xx, деление по значению может отправить их все в одну половину, и рекурсия не уменьшится. Деление по индексу всегда даёт половины размера ⌊n/2⌋\lfloor n/2 \rfloor и ⌈n/2⌉\lceil n/2 \rceil.
  • min(i + 8, ...) — это и есть «не больше 7 следующих». С проверкой break по yy лимит формально избыточен, но он делает сложность очевидной при чтении.

Разбор на примере

Точки после сортировки по xx: (2,3) (3,4) (5,1) | (12,10) (12,30) (40,50).

  • Левая тройка решается перебором: минимум 2\sqrt{2} между (2,3) и (3,4).
  • Правая тройка: минимум 2020 между (12,10) и (12,30).
  • d=2d = \sqrt{2}, mid_x = 12. В полосу ∣x−12∣<1.414|x - 12| < 1.414 попадают только (12,10) и (12,30) — обе из правой половины, расстояние 2020, улучшения нет.
  • Ответ 2\sqrt{2}.

На случайных данных полоса почти всегда тонкая, но корректность держится не на этом, а на оценке «7 соседей» — она верна для любых входов, включая точки на одной вертикали.

Сложность

  • Время: O(nlog⁡n)O(n \log n) — сортировка по xx плюс рекурсия с линейной склейкой.
  • Память: O(n)O(n) на списки by_y (на каждом уровне суммарно nn, и одновременно живут списки одной ветки) плюс O(log⁡n)O(\log n) на стек рекурсии.

Альтернатива: заметающая прямая

Тот же результат можно получить без рекурсии — через sweep line. Многие считают этот вариант проще в написании.

Идея

Сортируем точки по xx и идём слева направо. Пусть dd — лучший ответ среди уже просмотренных точек. Для новой точки pp кандидаты на пару ближе dd — только те, у кого:

  • x≥xp−dx \ge x_p - d — остальные слишком далеко слева, и следующие точки будут ещё правее, так что эти точки больше никогда не понадобятся;
  • ∣y−yp∣<d|y - y_p| < d.

Держим «активное окно» — точки, у которых xx не отстаёт от текущего больше чем на dd, упорядоченные по yy. Для новой точки:

  1. Удаляем из окна точки с x<xp−dx < x_p - d (указатель left идёт только вперёд, каждую точку удаляем один раз).
  2. Бинарным поиском находим в окне диапазон y∈[yp−d,yp+d]y \in [y_p - d, y_p + d] и сравниваем pp с каждой точкой из него.
  3. Добавляем pp в окно.

Тот же аргумент с квадратами показывает, что в прямоугольнике d×2dd \times 2d слева от pp лежит O(1)O(1) точек, так что шаг 2 стоит O(log⁡n)O(\log n) плюс константа.

Код

В стандартной библиотеке Python нет сбалансированного дерева, поэтому в примере окно — отсортированный список и bisect. Вставка и удаление в нём стоят O(n)O(n) из-за сдвига элементов, так что честные O(nlog⁡n)O(n \log n) получаются с SortedList из пакета sortedcontainers или с TreeSet/std::set в Java и C++. Для собеседования на Python это нормальный компромисс, если вы его проговорите.

import bisect import math def closest_pair_sweep(points): pts = sorted(points) # по x active = [] # (y, x) точек в окне шириной best, по возрастанию y best = math.inf left = 0 # самая левая точка, ещё лежащая в окне for x, y in pts: # Выкидываем точки, которые отстали по x больше чем на best while pts[left][0] < x - best: lx, ly = pts[left] active.pop(bisect.bisect_left(active, (ly, lx))) left += 1 # Кандидаты — только точки с y в [y - best, y + best] lo = bisect.bisect_left(active, (y - best, -math.inf)) hi = bisect.bisect_right(active, (y + best, math.inf)) for ay, ax in active[lo:hi]: best = min(best, math.dist((x, y), (ax, ay))) bisect.insort(active, (y, x)) return best pts = [(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)] print(closest_pair_sweep(pts)) # 1.4142135623730951

Обратите внимание: в окне храним пары (y, x), а не (x, y) — так список сортируется по yy, а xx разрешает ничьи и помогает найти нужный элемент при удалении. Дубликаты точек тоже обрабатываются: bisect_left находит и удаляет одну копию.

Какой вариант выбрать

КритерийРазделяй и властвуйSweep line
СложностьO(nlog⁡n)O(n \log n)O(nlog⁡n)O(n \log n) со сбалансированным деревом
Нужна структура данныхНет, только спискиУпорядоченное множество
РекурсияДа, глубина log⁡n\log nНет
Что сложнее объяснитьСлияние по yy и оценку полосыПочему окно маленькое
Онлайн-версияНетДа: точки можно добавлять по мере прихода по xx

В нашем замере на 200 000 случайных точек в [0,1]2[0, 1]^2 sweep-версия на Python с bisect работала примерно в 5 раз быстрее рекурсивной: на равномерных данных окно маленькое, и сдвиги в списке почти ничего не стоят, а рекурсия в Python дорогая. На данных, где окно разрастается (точки вдоль вертикали), картина может быть обратной. Цифры зависят от машины — воспринимайте их как порядок, а не как бенчмарк.

Ещё быстрее: сетка и рандомизация

Для полноты: существует рандомизированный подход с ожидаемым линейным временем — первым такой алгоритм предложил Майкл Рабин в 1976 году, позже появились более простые варианты. Точки перемешиваются и добавляются по одной, плоскость делится на клетки со стороной dd, клетки хранятся в хеш-таблице. Новую точку сравнивают только с точками из 9 соседних клеток; если ответ уменьшился — сетку перестраивают. На собеседовании достаточно знать, что такой подход есть, — писать его не просят.

Типичные ошибки

  1. Проверка только соседей в полосе. Сравнить точку лишь со следующей по yy недостаточно: ближайшая может быть третьей или пятой. Нужно до 7 следующих или цикл с break по разнице yy.
  2. Полоса по xx из всего массива. Если брать точки полосы из px, а не из отсортированного по yy списка, и сортировать заново, получится O(nlog⁡2n)O(n \log^2 n). Работает, но если вас спросят про оптимум — это не он.
  3. Не те границы полосы. Полоса — строго abs(x - mid_x) < d, отсечение по yy — >= d. Нестрогие варианты ответ не ломают, только расширяют перебор. Опасна обратная ошибка — сузить полосу до < d / 2 или взять d до того, как посчитаны обе половины.
  4. Квадратный корень в каждом сравнении. Корень не меняет порядок, поэтому сравнивать можно квадраты расстояний и извлечь корень один раз в конце. Это ещё и избавляет от погрешностей на целых координатах. В примерах выше math.dist оставлен для читаемости.
  5. Деление по значению mid_x. При множестве точек с одинаковым xx рекурсия не сокращается. Делите по индексу.
  6. Забытые дубликаты. Две одинаковые точки дают ответ 00, и код должен это переживать. Обе версии выше проверены на входах с повторами.

K Closest Points to Origin

Название похоже, но задача другая. LeetCode 973: дан массив точек points и число k, вернуть k точек, ближайших к началу координат (0,0)(0, 0), в любом порядке.

Здесь нет пар и нет геометрического трюка: у каждой точки одно число — расстояние до нуля. Это чистая задача top-k, родственная Top K Frequent Elements. Расстояние сравниваем по квадрату x2+y2x^2 + y^2, корень не нужен.

Сортировка — O(n log n)

def k_closest_sort(points, k): return sorted(points, key=lambda p: p[0] * p[0] + p[1] * p[1])[:k] print(k_closest_sort([[1, 3], [-2, 2]], 1)) # [[-2, 2]]

Одна строка, и для n≤104n \le 10^4 (ограничение в LeetCode 973) этого достаточно. На собеседовании назовите и сразу предложите улучшение.

Max-куча размера k — O(n log k)

Держим кучу из kk лучших кандидатов, на вершине — самый дальний из них. Новую точку кладём, только если она ближе вершины. В Python heapq — min-куча, поэтому храним расстояние со знаком минус.

import heapq def k_closest_heap(points, k): heap = [] # max-куча через отрицательные расстояния for x, y in points: d = x * x + y * y if len(heap) < k: heapq.heappush(heap, (-d, x, y)) elif d < -heap[0][0]: heapq.heapreplace(heap, (-d, x, y)) return [[x, y] for _, x, y in heap] print(k_closest_heap([[3, 3], [5, -1], [-2, 4]], 2)) # [[-2, 4], [3, 3]]

Плюсы: O(k)O(k) памяти и работа в потоке — точки можно читать по одной, не держа весь массив. Это стоит упомянуть: интервьюеры часто добавляют вопрос «а если точек миллиард и они не влезают в память?».

Quickselect — O(n) в среднем

Если массив в памяти и порядок ответа не важен, можно не сортировать, а разбить массив так, чтобы kk ближайших оказались в начале. Это quickselect по ключу «квадрат расстояния». Трёхпутевое разбиение защищает от деградации на множестве равных расстояний.

import random def k_closest_select(points, k): pts = points[:] dist = lambda p: p[0] * p[0] + p[1] * p[1] lo, hi = 0, len(pts) - 1 while lo < hi: pivot = dist(pts[random.randint(lo, hi)]) # Трёхпутевое разбиение: < pivot | == pivot | > pivot lt, i, gt = lo, lo, hi while i <= gt: d = dist(pts[i]) if d < pivot: pts[lt], pts[i] = pts[i], pts[lt] lt += 1 i += 1 elif d > pivot: pts[i], pts[gt] = pts[gt], pts[i] gt -= 1 else: i += 1 if k <= lt: hi = lt - 1 elif k > gt + 1: lo = gt + 1 else: break return pts[:k] print(k_closest_select([[1, 3], [-2, 2]], 1)) # [[-2, 2]]

После разбиения все точки левее lt ближе опорной, а на отрезке [lt, gt] лежат равные ей. Если kk-я позиция попала в этот отрезок — граница найдена, и первые kk элементов и есть ответ. Худший случай — O(n2)O(n^2), но случайный выбор опорного делает его практически недостижимым.

Сравнение подходов

ПодходВремяПамятьКогда выбирать
СортировкаO(nlog⁡n)O(n \log n)O(n)O(n)Быстро написать, нужен упорядоченный ответ
Max-кучаO(nlog⁡k)O(n \log k)O(k)O(k)k≪nk \ll n, поток данных, ограниченная память
QuickselectO(n)O(n) в среднемO(n)O(n)*Всё в памяти, порядок не важен, нужен максимум скорости

* Можно делать на месте, если разрешено менять входной массив.

Где встречается на собеседованиях

  • K Closest Points to Origin (LeetCode 973) — одна из самых частых задач на кучи. Ожидают решение кучей, хороший ответ — ещё и quickselect с оценкой обоих.
  • Ближайшая пара точек — реже как задача на код, чаще как вопрос на понимание «разделяй и властвуй»: выведите рекуррентное соотношение, объясните, почему склейка линейная, и откуда берётся 7. Если вы готовы к вопросам про оценку сложности рекурсивных алгоритмов, этот пример отлично ложится в разговор.
  • Вариации: ближайшая пара между двумя множествами (красные и синие точки), ближайшая пара в манхэттенской метрике, «есть ли пара ближе dd» — последнюю удобно решать сеткой из клеток со стороной dd за O(n)O(n) с хеш-таблицей.
  • Системный дизайн: «найти ближайших курьеров/водителей» — там те же идеи живут в виде геохешей, сеток и k-d деревьев, только на миллионах точек и с обновлениями в реальном времени.

Итог

Ближайшая пара точек — эталонный пример того, что в «разделяй и властвуй» трудность не в делении, а в склейке. Два наблюдения делают её линейной: кандидаты лежат в полосе шириной 2d2d, а в полосе каждой точке хватает 7 соседей по yy. Слияние по yy на подъёме рекурсии убирает лишний логарифм. Заметающая прямая даёт ту же оценку итеративно, если есть упорядоченное множество. А K Closest Points to Origin, несмотря на название, — задача про top-k: куча или quickselect, и никакой геометрии, кроме x2+y2x^2 + y^2.

Потренироваться в спокойной обстановке

Все задачи