점 사이의 최소 거리를 찾는 가장 빠른 방법

Question

나는 2D 점 집합이 있고 어떤 점 쌍이 집합에서 최단 거리인지를 알아내는 가장 빠른 방법을 찾아야합니다.

이 작업을 수행하는 최적의 방법은 무엇입니까? 내 접근 방식은 quicksort 그들을 정렬하고 거리를 계산하는 것입니다. 이것은 O (nlogn + n) = O (nlogn)입니다.

선형 시간으로 처리 할 수 ​​있습니까?

감사합니다. O (N^2)의 모든 지점 사이

Answer 1

번호 최소 거리 당신이 다른 모든 점에 대한 모든 지점을 비교해야하기 때문이다. 기술적으로 그것은 n * n/2입니다. 왜냐하면 단지 채우기를해야하기 때문에 매트릭스의 절반을 채워야하기 때문입니다.

주어진 포인트에 가장 가까운 이웃을 찾는 더 빠른 알고리즘이 있습니다. 불행하게도 가장 가까운 두 점을 찾기 위해 모든 점에 대해이 작업을 수행해야합니다.

Answer 2

It is actually :

가

점 문제의 가까운 쌍 쌍 문제가 computational geometry의 문제가 가까운 또는 : 거리 공간에 N 포인트 부여가 가장 작은 거리를 갖는 점 쌍을 찾기 그 (것)들 사이 ...

floor function가 일정 시간에서 계산 가능하다는 것을 전제로하는 계산 모델에서 문제는 O (n 로그 로그 n) 시간. 우리가 임의의 층의 기능과 함께 사용할 수 있도록하면 문제가

Answer 3

는 각 지점에서 일정한 금액을 프로브와 반복적 심화 DFS를 사용할 수 있다면, ... O (N) 시간이 해결 될 수있다 youd는 두 개의 가장 가까운 점보다 더 멀리 떨어져있는 것을 결코 확인하지 못합니다 ... 그리고 실패한 패스에 의존하지 않으므로 ID DFS의 경향을 재 계산할 필요가 없습니다.