Показать меню

Задача о паре ближайших точек

20.09.2022
46

Задача о паре ближайших точек — это задача вычислительной геометрии. Дано n точек в метрическом пространстве, нужно найти пару точек с наименьшим расстоянием между ними.

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

Наивный алгоритм нахождения расстояний между всеми парами в пространстве размерности d и выбора среди них наименьшего требует времени O(n2). Оказывается, что задача может быть решена за время O ( n log ⁡ n ) {displaystyle O(nlog n)} в евклидовом пространстве или Lp пространстве фиксированной размерности d. В модели вычислений алгебраического дерева решений алгоритм со временем O(n log n) оптимален при сведении от задачи единственности элемента. В вычислительной модели, в которой принимается, что функция floor вычисляема за постоянное время, задача может быть решена за время O ( n log ⁡ log ⁡ n ) {displaystyle O(nlog log n)} . Если мы позволяем применение рандомизации вместе с функцией floor, задача может быть решена за время O(n).

Алгоритм полного перебора

Пара ближайших точек может быть вычислена за время O(n2) путём выполнения полного перебора. Чтобы это сделать, можно вычислить расстояние между всеми n(n − 1) / 2 парами точек, затем выбрать пару с наименьшим расстоянием, как показано ниже.

minDist = infinity for i = 1 to length(P) - 1 for j = i + 1 to length(P) let p = P[i], q = P[j] if dist(p, q) < minDist: minDist = dist(p, q) closestPair = (p, q) return closestPair

Планарный случай

Задача может быть решена за время O ( n log ⁡ n ) {displaystyle O(nlog n)} с помощью рекурсивного подхода «разделяй и властвуй», например, так:

  • Сортируем точки согласно их x-координатам;
  • Разбиваем множество точек на два подмножества равного размера вертикальной прямой x = x m i d {displaystyle x=x_{mid}} ;
  • Решаем задачу рекурсивно на левой и на правой частях. Это приводит к левому минимальному расстоянию d L m i n {displaystyle d_{Lmin}} и правому минимальному расстоянию d R m i n {displaystyle d_{Rmin}} , соответственно;
  • Находим минимальное расстояние d L R m i n {displaystyle d_{LRmin}} среди пар точек, из которых одна точка лежит слева от вертикальной линии, а другая точка лежит справа от прямой;
  • Конечным ответом будет минимальное значение среди d L m i n {displaystyle d_{Lmin}} , d R m i n {displaystyle d_{Rmin}} и d L R m i n {displaystyle d_{LRmin}} .
  • Оказывается, что шаг 4 может быть выполнен за линейное время. Снова, наивный подход потребовал бы вычисление расстояний для всех пар слева/справа, то есть квадратичное время. Ключевое наблюдение основывается на следующем свойстве разреженности множества точек. Мы уже знаем, что пара ближайших точек не находятся на большем расстоянии, чем d i s t = min ( d L m i n , d R m i n ) {displaystyle mathrm {dist} =min(d_{Lmin},d_{Rmin})} . Поэтому, для каждой точки p слева от разделяющей прямой мы должны сравнить расстояния до точек, которые лежат в прямоугольнике с размерами (dist, 2 ⋅ dist) как показано на рисунке. И этот прямоугольник может содержать не более шести точек, попарное расстояние между которыми не менее d R m i n {displaystyle d_{Rmin}} . Таким образом, достаточно вычислить на 4-м шаге 6n расстояний. Рекуррентное отношение для числа шагов может быть записано как T ( n ) = 2 T ( n 2 ) + O ( n ) {displaystyle T(n)=2T({ frac {n}{2}})+O(n)} , которое может быть решено с помощью основной теоремы для рекурренции разделяй и властвуй, что даёт O ( n log ⁡ n ) {displaystyle O(nlog n)} .

    Так как пара ближайших точек определяют ребро в триангуляции Делоне и соответствуют двум смежным ячейкам в диаграмме Вороного, пара ближайших точек может быть определена за линейное время, если дана одна из этих двух структур. Вычисление триангуляции Делоне или диаграммы Вороного занимает время O ( n log ⁡ n ) {displaystyle O(nlog n)} . Эти подходы не эффективны для размерностей d>2, в то время как алгоритм «разделяй и властвуй» может быть обобщён до времени выполнения O ( n log ⁡ n ) {displaystyle O(nlog n)} для любого постоянного значения размерности d.

    Динамическая задача ближайшей пары

    Динамическая версия для задачи пары ближайших точек ставится следующим образом:

    • Если дано динамическое множество объектов, найти алгоритмы и структуры данных для эффективного перевычисления пары ближайших точек каждый раз, когда объект вставляется или удаляется.

    Если ограничивающий прямоугольник для всех точек заранее известен и доступна функция floor с постоянным временем работы, то была предложена структура данных с ожидаемой памятью O(n), которая поддерживает ожидаемое время (среднее время) вставки и удаления O(log n) и постоянное время запроса. Если задача модифицирована для модели алгебраического дерева принятия решения, вставки и удаления потребуют среднее время O ( log 2 ⁡ n ) {displaystyle O(log ^{2}n)} . Следует отметить, что сложность указанной выше динамической задачи о паре ближайших точек экспоненциально зависит от размерности d, поэтому алгоритм становится менее пригодным для задач высокой размерности.

    Алгоритм для динамической задачи пары ближайших точек в пространстве размерности d разработал Сергей Беспамятных в 1998 году. Точки могут быть вставлены и удалены за время O(logn) на одну точку (в худшем случае).

    Еще по этой теме:
    Сведение (теория сложности вычислений)
    13:00, 17 апрель
    Сведение (теория сложности вычислений)
    Сведение в теории сложности вычислений — преобразование одной задачи к другой. В общем случае, для алгоритма, преобразующего экземпляры задачи P
    Конфигурация Мёбиуса — Кантора
    22:01, 24 ноябрь
    Конфигурация Мёбиуса — Кантора
    Конфигурацией Мёбиуса — Кантора — конфигурация, состоящая из восьми точек и восьми прямых, такая, что на каждой прямой лежат по три точки и через каждую точку проходят по три прямые. Невозможно
    Экзистенциальная теория вещественных чисел
    21:00, 14 май
    Экзистенциальная теория вещественных чисел
    Экзистенциальная теория вещественных чисел — это множество всех верных утверждений вида ∃ X 1
    Теория квантовой сложности
    14:36, 13 декабрь
    Теория квантовой сложности
    Квантовая теория сложности — часть теории сложности вычислений в теоретической информатике. Изучает классы сложности, определённые с использованием квантовых компьютеров и квантовой информации, а
    APX
    08:20, 02 декабрь
    APX
    APX (от англ. «approximable») в теории вычислительной сложности — это класс NP-трудных задач, для которых существуют аппроксимационные алгоритмы полиномиальной сложности с постоянным коэффициентом
    Окружность Аполлония
    01:13, 02 декабрь
    Окружность Аполлония
    Окружность Аполлония — геометрическое место точек плоскости, отношение расстояний от которых до двух заданных точек — величина постоянная, не равная единице. Биполярные координаты — ортогональная
    Комментарии:
    Добавить комментарий
    Ваше Имя:
    Ваш E-Mail: