가장 가까운 쌍 포인트 알고리즘의 변형

Question

가장 가까운 쌍 포인트 문제는 계산 지오메트리에서 잘 알려져 있습니다. 주어진 점 목록 (x, y)은 유클리드 거리가 가장 작은 점 쌍을 찾습니다. 이제이 문제에 대한 변형이 있습니다. n 점 (xi, yi) (n + 1> i> 0)의 목록이 주어지면 각 점 (xi, yi)에 가장 가까운 유클리드 거리를 찾아서 모든 점에 대한 평균 가장 가까운 유클리드 거리.

all_distance = []; 
for i= 1 to n 
    p = (xi,yi); 
    dis = []; 
    for j= 1 to n 
     if j==i 
      continue; 
     else 
      q = (xj,yj); 
      pt_dis = distance(p,q); 
     end 
     dis = [dis; pt_dis]; 
    end 
    all_distance = [all_distance; nearest(dis)] 

end 
mean_distance = all_distance/n; 

이 방법은 간단하지만 계산 오히려 느린 : 나는 무차별 방법을 알고있다. 이 문제를 해결할 수있는 빠른 알고리즘이 있는지 궁금합니다. 감사!

Answer 1

이 문제는 일반적으로 kd-tree 또는 quadtree으로 가장 잘 해결되지만, 빠른 속도로 더러워지기를 원할 경우 포인트를 버켓팅해야합니다. 즉, 귀하의 포인트가 (0,0)에서 (10,10) 사이의 범위에 대략 균등하게 분포되어 있다고 가정 할 경우이 경우 100 개의 버켓에 대해 1 단위 평방의 버킷을 만들 수 있습니다. 이제 버킷에서 가장 가까운 점과 인접한 8 개의 버킷을 모두 찾아 포인트를 처리합니다. 1 단위 또는 그 이하의 점을 발견하면 가까운 점이 인접한 버킷 중 하나에 있지 않아야하므로 가장 가까운 점임을 알 수 있습니다. 즉, 1 단위 이상 떨어져 있어야합니다. 가까운 지점을 찾지 못하면 모든 포인트를 확인하거나 다음 번 버킷 고리로 확장 할 수 있습니다.

Answer 2

O (n log n) 시간에 Delaunay triangulation을 계산할 수 있으며 각 꼭지점에 가장 가까운 점은 삼각 측량의 인접 점 중 하나가됩니다. 조사 할 O (n) 개의 전체 에지가 있으므로 O (n log n) 삼각 측량 비용이 우세합니다.