Найти две ближайшие точки в 2D распределении

Question

Я ищу алгоритм, чтобы найти две ближайшие точки в списке 2D точек (каждая точка имеет атрибуты x и y).

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

Тем не менее, я подумал, что, возможно, кто-то, кто знает больше о kd-деревьях или индексах высокой размерности, таких как сортировка, созданная для создания приближенных деревьев поиска ближайших соседей, мог бы стать лучшим решением этой проблемы, поэтому я хотел бы спросить:

Существуют ли интеллектуальные / известные алгоритмы для эффективного вычисления двух ближайших точек в (2D) распределении? Любые предложения, которые могут предложить другие на этом фронте, были бы чрезвычайно полезны!

Answer 1

Классический подход Divide & Conquer работает во времени O (n log (n)). https://en.wikipedia.org/wiki/Closest_pair_of_points_problem

. Внимательно посмотрите на Примечание 3 и найдите алгоритм Рабина.

Answer 2

Это хорошо известная проблема в конкурентном программировании. Вот моя реализация для этого.

#include <iostream>
#include <algorithm>
#include <utility>
#define x first
#define y second
#define INF 100000000

using namespace std;

int n;

typedef pair<int, int> point;

point tab1[100000];
point tab2[100000];

long long distance(point a, point b){
    return abs(a.x - b.x) + abs(a.y - b.y);
}

long long closestpair(int p, int k){
    if(p == k){
        return INF;
    }
    if(k - p == 1){
        return distance(tab1[p], tab1[k]);
    }
    int mid = (p + k) / 2;
    int count = 1;
    long long dl = closestpair(p, mid - 1);
    long long dp = closestpair(mid, k);
    long long len = min(dl, dp);

    for(int i = p; i <= k; i++){
        if(abs(tab1[i].x - tab1[mid].x) <= len){
            tab2[count] = make_pair(-tab1[i].y, tab1[i].x);
            count++;
        }
    }
    sort(tab2 + 1, tab2 + count + 1);
    for(int i = 1; i < count; i++){
        for(int j = i + 1; j < min(7, count - 1); j++){
            len = min(len, distance(tab2[i], tab2[j]));
        }
    }
    return len;
}

int main(){
    cin >> n;
    for(int i = 1; i < n + 1; i++){
        cin >> tab1[i].x >> tab1[i].y;
    }
    sort(tab1 + 1, tab1 + n + 1);
    cout << closestpair(1, n);
    return 0;
}

Я нашел какое-то объяснение здесь