В чём идея алгоритма поиска ближайшей пары точек за O(n log n)?
Нужно найти две ближайшие точки среди n точек на плоскости. Наивно это O(n^2). Слышал, что есть метод «разделяй и властвуй» за O(n log n), но не понимаю, как после деления пополам учесть пары, которые оказались по разные стороны от линии раздела. В чём ключевая идея?
2 ответа
Метод «разделяй и властвуй»:
- Сортируем точки по x. Делим вертикальной прямой пополам.
- Рекурсивно находим минимальное расстояние
dв левой и правой половинах, берёмd = min(dL, dR). - Ключевой шаг — «полоса»: остаётся проверить пары, где одна точка слева, другая справа. Но интересны только точки в вертикальной полосе шириной
2dвокруг линии раздела — за её пределами расстояние заведомо большеd. - Точки полосы сортируем по y. Тут магия: для каждой точки достаточно сравнить её лишь с несколькими следующими по y (доказуемо не более ~7), потому что в прямоугольнике d×2d не может уместиться больше константного числа точек на расстоянии ≥ d друг от друга.
// псевдокод одного уровня рекурсии
double solve(points sorted by x) {
if (n <= 3) return bruteForce();
разделить на L и R по середине x;
double d = min(solve(L), solve(R));
собрать точки в полосе |x - midX| < d;
отсортировать полосу по y;
для каждой точки полосы сравнить со следующими ~7 по y, обновить d;
return d;
}
Именно ограничение «≤ const сравнений на точку в полосе» превращает потенциально квадратичный шаг полосы в линейный, и общая сложность выходит O(n log n).
Почему именно константа сравнений в полосе: если бы в прямоугольнике d×2d было много точек, какие-то две оказались бы ближе d — а это противоречит тому, что d уже минимум внутри половин. Геометрически в такой прямоугольник влезает не больше ~8 точек, попарно удалённых на ≥ d. Отсюда «проверь следующие 7 по y».
Практические грабли:
- Сравнивай квадраты расстояний (целые!), а не сами расстояния — никаких
sqrtв горячем цикле, точно и быстро. - Чтобы каждый уровень рекурсии не пересортировывал по y за O(n log n) (иначе будет O(n log^2 n)), поддерживай сортировку по y слиянием снизу вверх — тогда честные O(n log n).
- Альтернатива на контестах — рандомизированный sweep line / хеш-сетка по ячейкам со стороной d: проще кодить и в среднем O(n). Но классический D&C — каноничный детерминированный ответ.