Поиск пары ближайших точек методом декомпозиции - EcsFlash/DataTypes GitHub Wiki

image image image image image

Те же яйца только в профиль:

Общая идея

Задача заключается в нахождении двух точек из заданного множества точек на плоскости, расстояние между которыми минимально. Метод декомпозиции разбивает задачу на меньшие подзадачи, решает их рекурсивно и объединяет результаты, минимизируя вычисления.

Алгоритм поиска ближайшей пары точек методом декомпозиции

  1. Разделение:
    • Сортируем точки по x -координате (однократно, перед началом рекурсии).
    • Делим множество точек на две равные части по медиане x -координаты, получая левую и правую половины.
  2. Рекурсивное решение:
    • Решаем задачу для левой и правой половин, находя минимальные расстояния d_L и d_R.
    • Минимальное расстояние среди подзадач: d = min(d_L, d_R).
  3. Объединение:
    • Рассматриваем точки в полосе шириной 2 * delta вокруг медианы (точки с x -координатами в интервале [x_m - d, x_m + d], где x_m — медиана).
    • Для каждой точки в этой полосе проверяем расстояние до ограниченного числа соседних точек (не более 7 в двумерном случае), отсортированных по y -координате.
    • Обновляем минимальное расстояние, если найдена пара ближе, чем d.
  4. База рекурсии:
    • Если в подмножестве 2 или 3 точки, используем грубую силу для вычисления расстояний.
    • Если 1 точка, возвращаем бесконечное расстояние.

Ключевые аспекты

  • **Сортировка по y **: Для оптимизации проверки в полосе точки в этой области сортируются поy -координате, чтобы ограничить количество проверяемых пар.
  • Ограничение числа проверок: Для каждой точки в полосе достаточно проверить не более 7 ближайших точек по y, так как точки, расположенные дальше, не могут дать расстояние меньше d (геометрическое свойство двумерной плоскости).

Сложность

  • Временная сложность: O(n log n)
    • Сортировка по x : O(n log n).
    • Рекурсивные вызовы: T(n) = 2T(n/2) + O(n), что по теореме даёт O(n log n).
    • Проверка полосы: O(n) , так как для каждой точки проверяется ограниченное число соседей.
  • Пространственная сложность: O(n) для хранения точек и полосы.

Сравнение с методом грубой силы

Характеристика Грубая сила Декомпозиция
Временная сложность ( O(n^2) ) ( O(n \log n) )
Пространственная сложность ( O(1) ) ( O(n) )
Простота реализации Простая Более сложная
Применение Малые наборы точек Большие наборы точек