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

Задача о паре ближайших точек — это задача вычислительной геометрии. Дано 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 парами точек, затем выбрать пару с наименьшим расстоянием, как показано ниже.

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

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

Оказывается, что шаг 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) на одну точку (в худшем случае).