각 세트에서 가장 가까운 두 세트의 점의 가장 가까운 쌍

Question

두 세트의 포인트 A와 B가 있으며 각 세트에서 한 포인트가 추출되는 가장 가까운 포인트 쌍을 찾으려고합니다. 즉, 두 선을 그리는 점을 사용하려면 두 선 사이에 가장 짧은 선분을 그릴 수있는 두 점이 필요합니다.

주위를 둘러 보니 거의 모든 것이 1 세트에서 가장 가까운 포인트를 찾는 것으로 나타납니다. 과도한 것 같아 보로 노이 테셀레이션을 추천하는 해결책을 찾았지만 O (n^2)보다 조금 더 좋은 것을 찾고 있습니다.

두 세트는 폼 라인을 비교하고 있지만 반드시 똑같지는 않지만 C#으로 작성하고 있습니다.

감사합니다.

Answer 1

고전적인 D & C 알고리즘 (위키 피 디아 링크에서 설명)을 적용하여 모든 점을 함께 처리하고 추가 비트로 태그를 지정할 수 있습니다.

모든 세트의 구성원 만 후보 왼쪽 - 오른쪽 쌍을 허용하도록 병합 단계를 수정해야합니다. 이렇게하면 재귀 함수는 가장 가까운 A-B 쌍을 반환합니다. O (N.Log (N)) 동작은 보존되어야합니다.

"점선"에 점/선 거리 (또는 선/선 교차점)가 신속하게 평가 될 수 있도록 알려진 방정식이있는 경우 더 빠른 해결책이있을 수 있습니다.