Ближайшая пара точек: разделяй и властвуй за O(n log n) и sweep line
Задача о ближайшей паре точек: от перебора за O(n²) к «разделяй и властвуй» за O(n log n), почему в полосе хватает 7 соседей, решение заметающей прямой и K Closest Points to Origin.
Коротко
| Что | Суть |
|---|---|
| Задача | Даны точек на плоскости, найти минимальное расстояние между двумя из них |
| Перебор | Все пары, — честно, но на точек это сравнений |
| Разделяй и властвуй | Режем по медиане , решаем половины, склеиваем через узкую полосу — |
| Главный трюк | В полосе каждую точку достаточно сравнить максимум с 7 следующими по |
| Sweep line | Идём слева направо, держим окно точек шириной , упорядоченное по — тоже |
| Родственная задача | K Closest Points to Origin — не про пары, а про top-k: куча или quickselect |
Ближайшая пара точек — классика из учебников (она есть в CLRS в главе про вычислительную геометрию) и любимый пример «разделяй и властвуй», где самое интересное происходит не в рекурсии, а на этапе склейки. На собеседованиях её саму дают нечасто, зато вопрос «почему там именно 7?» любят задавать, чтобы проверить, понимаете ли вы доказательства, а не только заучили код. А вот K Closest Points to Origin (LeetCode 973) встречается постоянно — разберём и её, потому что их часто путают.
Постановка задачи
На входе — список точек , . Нужно найти
Точки могут совпадать — тогда ответ . Координаты могут быть дробными. Иногда просят вернуть саму пару, а не расстояние; это меняет код на пару строк.
Пример: для точек (2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4) ответ — , пара (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
пар, времени, памяти. Для этого хватает, и на собеседовании это правильный первый шаг: назовите его, оцените и переходите к улучшению. Ещё он пригодится как эталон для стресс-тестов — без него ошибку в оптимальной версии почти не найти.
Интуиция: что даёт сортировка
В одномерном случае задача тривиальна: отсортируй числа, и ближайшая пара обязательно окажется соседней. .
На плоскости так не работает. Точки, соседние по , могут быть далеко по , а настоящая ближайшая пара — разнесена в отсортированном по массиве на сотни позиций. Сортировка по одной координате не спасает, но подсказывает идею: если разрезать множество вертикальной прямой, то пары делятся на три вида — обе точки слева, обе справа и «через разрез». Первые два вида — та же задача меньшего размера. Весь вопрос в третьем.
Разделяй и властвуй
Схема
- Сортируем точки по один раз в начале.
- Делим массив пополам по индексу. Пусть
mid_x— координата средней точки, это вертикальная прямая разреза. - Рекурсивно находим — ответ для левой половины и — для правой. Пусть .
- Ищем пары «через разрез», которые ближе . Если нашли — обновляем .
Шаг 4 и есть вся магия. Наивно он стоит , и тогда рекурсия даёт те же . Надо сделать его линейным.
Полоса шириной 2d
Первое наблюдение: если пара «через разрез» ближе , то обе её точки лежат не дальше от прямой разреза по горизонтали. Иначе одна только разница по уже больше . Значит, рассматривать можно только точки из полосы .
Но этого мало: в полосу могут попасть вообще все точки — например, если они выстроены вдоль вертикальной линии. Нужно второе наблюдение.
Второе наблюдение: упорядочим точки полосы по . Для точки интересны только те, у которых больше на величину меньше (пары «вниз» мы уже проверили, когда смотрели с другой точки). И таких точек мало — не больше 7.
Почему в полосе достаточно 7 соседей
Это то место, которое стоит уметь объяснить на доске.
Возьмём точку из полосы. Все интересные для неё точки лежат в прямоугольнике шириной (вся полоса) и высотой (от до ). Разрежем этот прямоугольник на 8 квадратов со стороной : 4 слева от разреза и 4 справа.
mid_x | +----+----+----+----+ y_p + d | | | | | +----+----+----+----+ | | | | | +----+----+----+----+ y_p <-------- 2d ------->
Каждый маленький квадрат целиком лежит в одной половине. Его диагональ равна . Значит, в нём не может быть двух точек из одной половины: иначе расстояние между ними было бы меньше , а мы знаем, что внутри каждой половины все пары не ближе (это и есть и ). Итого в прямоугольнике не больше 8 точек, одна из которых — сама . Остаётся максимум 7 кандидатов.
Отсюда и правило в коде: для каждой точки полосы смотрим не дальше 7 следующих по . Константа не обязана быть точной — в разных учебниках встречаются 5, 6, 7 и даже 15, в зависимости от того, насколько аккуратно оценивают. Важно, что она не зависит от , и проход по полосе становится линейным.
На практике удобнее не считать до 7, а прерывать внутренний цикл, как только разница по достигла : дальше точки только выше. Это работает и без явного лимита, а оценка выше гарантирует, что цикл короткий.
Откуда берётся O(n log n), а не O(n log² n)
Если на каждом уровне рекурсии сортировать полосу по заново, склейка стоит , и общее время получается
Это уже хорошо, но не оптимально. Трюк — тот же, что в сортировке слиянием: пусть рекурсия возвращает не только ответ, но и свои точки, отсортированные по . Тогда на уровне выше эти два списка сливаются за , и
По сути, мы одновременно сортируем точки по слиянием и решаем исходную задачу.
Код
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 точки, их проще перебрать. Если сделать базу «одна точка», придётся обрабатывать в полосе и аккуратнее делить.
- Делим по индексу, а не по значению
mid_x. Если много точек с одинаковым , деление по значению может отправить их все в одну половину, и рекурсия не уменьшится. Деление по индексу всегда даёт половины размера и . min(i + 8, ...)— это и есть «не больше 7 следующих». С проверкойbreakпо лимит формально избыточен, но он делает сложность очевидной при чтении.
Разбор на примере
Точки после сортировки по : (2,3) (3,4) (5,1) | (12,10) (12,30) (40,50).
- Левая тройка решается перебором: минимум между
(2,3)и(3,4). - Правая тройка: минимум между
(12,10)и(12,30). - ,
mid_x = 12. В полосу попадают только(12,10)и(12,30)— обе из правой половины, расстояние , улучшения нет. - Ответ .
На случайных данных полоса почти всегда тонкая, но корректность держится не на этом, а на оценке «7 соседей» — она верна для любых входов, включая точки на одной вертикали.
Сложность
- Время: — сортировка по плюс рекурсия с линейной склейкой.
- Память: на списки
by_y(на каждом уровне суммарно , и одновременно живут списки одной ветки) плюс на стек рекурсии.
Альтернатива: заметающая прямая
Тот же результат можно получить без рекурсии — через sweep line. Многие считают этот вариант проще в написании.
Идея
Сортируем точки по и идём слева направо. Пусть — лучший ответ среди уже просмотренных точек. Для новой точки кандидаты на пару ближе — только те, у кого:
- — остальные слишком далеко слева, и следующие точки будут ещё правее, так что эти точки больше никогда не понадобятся;
- .
Держим «активное окно» — точки, у которых не отстаёт от текущего больше чем на , упорядоченные по . Для новой точки:
- Удаляем из окна точки с (указатель
leftидёт только вперёд, каждую точку удаляем один раз). - Бинарным поиском находим в окне диапазон и сравниваем с каждой точкой из него.
- Добавляем в окно.
Тот же аргумент с квадратами показывает, что в прямоугольнике слева от лежит точек, так что шаг 2 стоит плюс константа.
Код
В стандартной библиотеке Python нет сбалансированного дерева, поэтому в примере окно — отсортированный список и bisect. Вставка и удаление в нём стоят из-за сдвига элементов, так что честные получаются с 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) — так список сортируется по , а разрешает ничьи и помогает найти нужный элемент при удалении. Дубликаты точек тоже обрабатываются: bisect_left находит и удаляет одну копию.
Какой вариант выбрать
| Критерий | Разделяй и властвуй | Sweep line |
|---|---|---|
| Сложность | со сбалансированным деревом | |
| Нужна структура данных | Нет, только списки | Упорядоченное множество |
| Рекурсия | Да, глубина | Нет |
| Что сложнее объяснить | Слияние по и оценку полосы | Почему окно маленькое |
| Онлайн-версия | Нет | Да: точки можно добавлять по мере прихода по |
В нашем замере на 200 000 случайных точек в sweep-версия на Python с bisect работала примерно в 5 раз быстрее рекурсивной: на равномерных данных окно маленькое, и сдвиги в списке почти ничего не стоят, а рекурсия в Python дорогая. На данных, где окно разрастается (точки вдоль вертикали), картина может быть обратной. Цифры зависят от машины — воспринимайте их как порядок, а не как бенчмарк.
Ещё быстрее: сетка и рандомизация
Для полноты: существует рандомизированный подход с ожидаемым линейным временем — первым такой алгоритм предложил Майкл Рабин в 1976 году, позже появились более простые варианты. Точки перемешиваются и добавляются по одной, плоскость делится на клетки со стороной , клетки хранятся в хеш-таблице. Новую точку сравнивают только с точками из 9 соседних клеток; если ответ уменьшился — сетку перестраивают. На собеседовании достаточно знать, что такой подход есть, — писать его не просят.
Типичные ошибки
- Проверка только соседей в полосе. Сравнить точку лишь со следующей по недостаточно: ближайшая может быть третьей или пятой. Нужно до 7 следующих или цикл с
breakпо разнице . - Полоса по из всего массива. Если брать точки полосы из
px, а не из отсортированного по списка, и сортировать заново, получится . Работает, но если вас спросят про оптимум — это не он. - Не те границы полосы. Полоса — строго
abs(x - mid_x) < d, отсечение по —>= d. Нестрогие варианты ответ не ломают, только расширяют перебор. Опасна обратная ошибка — сузить полосу до< d / 2или взятьdдо того, как посчитаны обе половины. - Квадратный корень в каждом сравнении. Корень не меняет порядок, поэтому сравнивать можно квадраты расстояний и извлечь корень один раз в конце. Это ещё и избавляет от погрешностей на целых координатах. В примерах выше
math.distоставлен для читаемости. - Деление по значению
mid_x. При множестве точек с одинаковым рекурсия не сокращается. Делите по индексу. - Забытые дубликаты. Две одинаковые точки дают ответ , и код должен это переживать. Обе версии выше проверены на входах с повторами.
K Closest Points to Origin
Название похоже, но задача другая. LeetCode 973: дан массив точек points и число k, вернуть k точек, ближайших к началу координат , в любом порядке.
Здесь нет пар и нет геометрического трюка: у каждой точки одно число — расстояние до нуля. Это чистая задача top-k, родственная Top K Frequent Elements. Расстояние сравниваем по квадрату , корень не нужен.
Сортировка — 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]]
Одна строка, и для (ограничение в LeetCode 973) этого достаточно. На собеседовании назовите и сразу предложите улучшение.
Max-куча размера k — O(n log k)
Держим кучу из лучших кандидатов, на вершине — самый дальний из них. Новую точку кладём, только если она ближе вершины. В 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]]
Плюсы: памяти и работа в потоке — точки можно читать по одной, не держа весь массив. Это стоит упомянуть: интервьюеры часто добавляют вопрос «а если точек миллиард и они не влезают в память?».
Quickselect — O(n) в среднем
Если массив в памяти и порядок ответа не важен, можно не сортировать, а разбить массив так, чтобы ближайших оказались в начале. Это 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] лежат равные ей. Если -я позиция попала в этот отрезок — граница найдена, и первые элементов и есть ответ. Худший случай — , но случайный выбор опорного делает его практически недостижимым.
Сравнение подходов
| Подход | Время | Память | Когда выбирать |
|---|---|---|---|
| Сортировка | Быстро написать, нужен упорядоченный ответ | ||
| Max-куча | , поток данных, ограниченная память | ||
| Quickselect | в среднем | * | Всё в памяти, порядок не важен, нужен максимум скорости |
* Можно делать на месте, если разрешено менять входной массив.
Где встречается на собеседованиях
- K Closest Points to Origin (LeetCode 973) — одна из самых частых задач на кучи. Ожидают решение кучей, хороший ответ — ещё и quickselect с оценкой обоих.
- Ближайшая пара точек — реже как задача на код, чаще как вопрос на понимание «разделяй и властвуй»: выведите рекуррентное соотношение, объясните, почему склейка линейная, и откуда берётся 7. Если вы готовы к вопросам про оценку сложности рекурсивных алгоритмов, этот пример отлично ложится в разговор.
- Вариации: ближайшая пара между двумя множествами (красные и синие точки), ближайшая пара в манхэттенской метрике, «есть ли пара ближе » — последнюю удобно решать сеткой из клеток со стороной за с хеш-таблицей.
- Системный дизайн: «найти ближайших курьеров/водителей» — там те же идеи живут в виде геохешей, сеток и k-d деревьев, только на миллионах точек и с обновлениями в реальном времени.
Итог
Ближайшая пара точек — эталонный пример того, что в «разделяй и властвуй» трудность не в делении, а в склейке. Два наблюдения делают её линейной: кандидаты лежат в полосе шириной , а в полосе каждой точке хватает 7 соседей по . Слияние по на подъёме рекурсии убирает лишний логарифм. Заметающая прямая даёт ту же оценку итеративно, если есть упорядоченное множество. А K Closest Points to Origin, несмотря на название, — задача про top-k: куча или quickselect, и никакой геометрии, кроме .