가장 가까운 점 쌍 문제

가장 가까운 점 쌍의 문제 또는 가장 가까운 쌍의 문제는 계산 기하학의 문제다: 미터법 공간에서$$n {\$displaystyle n}$개의$$ 점을 주어진 경우, 그들 사이의 거리가 가장 작은 점을 찾는다.유클리드 평면에서^[1] 포인트에 대한 가장 가까운 쌍 문제는 기하학적 알고리즘의 계산 복잡성에 대한 체계적 연구의 기원에서 다루어진 최초의 기하학적 문제들 중 하나이다.

시간 범위

유클리드 공간에서는 문제를 선형 시간 내에 해결하는 임의화된 알고리즘이 알려져 있으며, 유클리드 공간에서는 치수가 점증적 분석을 위한 상수로 처리된다.^[2][3][4]이는 모든 점 쌍 사이의 거리를 찾고 가장 작은 점을 선택하는 순진한 알고리즘에 의해 얻을 $수{\displaystyle }$ 있는 O${\displaystyle }$( ${\displaystyle {n\mathrm{}}^{}}$ 2${\displaystyle {}^{}}$) ${\displaystyle O(n^{2})$ 시간$$(여기서 큰 O 표기법)보다 상당히 빠르다.

플로어 기능을 사용할 수 있는 무제한 메모리가 있는 연산의 랜덤 액세스 머신 모델에서도 거의 선형 $O{\displaystyle (n}$ ${\displaystyle \log }$ ${\displaystyle }$ ${\displaystyle \log }$ $){\displaystyle O(n\log \log n)}$시간$$ 내에 무작위화 없이 문제를 해결할 수 있다.^[5]대수적 의사결정 트리와 같이 훨씬 제한된 연산 모델에서 문제는 다소 느린 $O{\displaystyle (n}$ ${\displaystyle \log \mathrm{logn}}$) ${\displaystyle O(n\log$ n$)}$의 시간 한계로 해결할 수 있으며,^[6] 이는 요소 고유성 문제에서 감소를 통해 이 모델에 최적이다.이러한 느린 시간 바인딩을 가진 스위프 라인 알고리즘과 분할 및 변환 알고리즘 모두 이러한 알고리즘 설계 기법의 예로서 일반적으로 학습된다.^[7][8]

선형 시간 랜덤화 알고리즘

Richard Lipton에 의해 약간 수정된 Rabin(1976년)의 선형 기대 시간 무작위 알고리즘은 $k{\displaystyle }$ ${\displaystyle k}$ -차원$$ 유클리드 공간의 $n{\displaystyle }$ ${\displaystyle n}$ 포인트로$$ 구성된$$ 입력 $세트{\displaystyle }$ S ${\\\displaystyty S}$에서 다음과 같이 진행된다.

1. $n{\displaystyle }$ ${\displaystyle n}$개의$$ 점 쌍을 임의로 선택하고 교체한 $후{\displaystyle }$ d ${\displaystyle d}$을(를) 선택한 쌍의 최소 거리로 설정하십시오$$.
2. 입력 지점을 $d{\displaystyle }$ ${\displaystyle d$ 크기의 사각형 점 그리드로 반올림하고 해시 테이블을 사용하여 동일한 그리드 점으로 반올림하는 입력 지점 쌍을 함께 수집하십시오.
3. 각 입력 지점에 대해 동일한 그리드 포인트로 반올림하거나 그리드$$ 포인트를 ${\displaystyle \mathrm{둘러싼}}$ ${\displaystyle {3k}^{}}$- 1 ${\displaystyle$ 3$^{k}-1의$Moore 인접 지역 내에 있는 다른 그리드 포인트로 반올림하는 다른 모든 입력에 대한 거리를 계산하십시오.
4. 이 프로세스에서 계산한 거리 중 가장 작은 거리를 반환하십시오.

알고리즘은 거리 $d{\displaystyle }$ ${\displaystyle d}$보다 가까운 쌍을 동일한 격자점 또는 인접 격자점에$$ 매핑하기 때문에 항상 가장 가까운 쌍을 정확하게 결정한다.알고리즘의 첫 번째 단계에서 쌍의 균일한 샘플링(비슷한 수의 쌍을 샘플링하기 위해 다른 방법인 라빈과 비교)은 알고리즘에 의해 계산된 예상 거리 수가 선형이라는 증거를 단순화한다.^[4]

대신 다른 알고리즘 Khuller & Matias(1995)는 두 가지 단계를 거친다$:$ ${\displaystyle 2k\sqrt{}}${\$displaystyle$ 2${\sqrt{k}$의 근사치 내에서 가장 가까운 거리에 근접한 거리에 근접한 무작위 반복 필터링 프로세스와 이 근사 거리를 정확히 가장 가까운 거리로 바꾸는 마무리 단계.필터링 프로세스는 $S{\displaystyle }$ ${\displaystyle S}$이(가) 비워질$$ 때까지 다음 단계를 반복한다.

1. $S{\displaystyle }$ ${\displaystyle S}$에서 임의로 $점{\displaystyle }$ p ${\displaystyle p}$을(를) 선택하십시오$.$
2. $p{\displaystyle }$ ${\displaystyle p}$에서 $S{\displaystyle }$ ${\displaystyle S}$의 다른 모든 지점까지의$$ 거리를 계산하고$$ $d{\displaystyle }$ ${\displaystyle d}$을(를) 최소 그러한 거리로 한다$$.
3. 입력 지점을 크기 $d{\displaystyle }$/${\displaystyle }$( ${\displaystyle 2}$ ${\displaystyle k}$) ${\displaystyle$ d$/(2{\sqrt{k$의 사각 그리드로 반올림하고 Moore 인접 영역에 다른 포인트가 없는$$ $모든{\displaystyle }$ 포인트를 S ${\displaystyle S}$에서 삭제하십시오.

이 필터링 프로세스에 의해 발견된 대략적인 거리는 $S{\displaystyle }$ ${\displaystyle S}$이(가) 비어지기$$ 전의 단계에서 계산된$$$d{\displaystyle }$ ${\displaystyle d}$의 최종 값이다.각 단계는 예상 점의 최소 절반인 $d{\displaystyle }$ ${\displaystyle d}$ 이상의$$ 가장 가까운 인접 점이 있는 모든 점을 제거하며, 여기서 필터링에 대한 총 예상 시간은 선형이다.$일단{\displaystyle }$ d$${\$displaystyle d$}의 대략적인 값이$$ 알려지면 라빈 알고리즘의 최종 단계에 사용할 수 있다. 이 단계에서 각 격자점은 그것과 반올림한 입력 수를 일정하게 가지므로, 다시 한 번 시간은 선형이다.^[3]

동적 근거리 무선 문제

가장 가까운 페어 문제에 대한 동적 버전은 다음과 같이 명시된다.

• 동적 객체 집합이 주어진 경우 객체를 삽입하거나 삭제할 때마다 가장 가까운 객체 쌍의 효율적인 재계산을 위한 알고리즘과 데이터 구조를 찾으십시오.

모든 포인트에 대한 경계 상자를 미리 알고 일정 시간 플로어 기능을 사용할 수 있는 경우 예상 $O{\displaystyle }$( n${\displaystyle }$) ${\displaystyle O(n)}$ -공간$$ 데이터 구조를 제안하여 예상 $시간{\displaystyle }$ O${\displaystyle }$( ${\displaystyle \mathrm{로그}}$ ${\displaystyle }$ n${\displaystyle }$) ${\displaystyle O(\log n)}$ 삽입$$ 및 삭제와 일정한 쿼리 시간을 지원하였다.대수적 의사결정 트리 모델에 대해 수정했을 때, 삽입과 $삭제$는 O${\displaystyle ({log\mathrm{}}^{}}$ 2${\displaystyle {}^{}\mathrm{nn}}$ ${\displaystyle )}$ ${\displaystyle O(\log ^{$2}$n)}$의 예상 시간을 필요로 한다.^[9]위에서 인용한 동적 가장 가까운 쌍 알고리즘의 복잡성은 차원 $d{\displaystyle }$ ${\displaystyle$ d$\}$에서 기하급수적이므로 그러한 알고리즘은 고차원적인 문제에 적합하지 않게 된다.

$d{\displaystyle }$ ${\displaystyle d}$차원$$ 공간의 동적 가장 근접한 쌍 문제에 대한 알고리즘은 1998년 Sergey Bespamyatnikh에 의해 개발되었다.^[10]포인트당 (최악의 경우) $O{\displaystyle (\mathrm{로그}}$ $){\displaystyle$ O$(\log n)}$번으로$$ 포인트를 삽입 및 삭제할 수 있다.

참고 항목

• GIS
• 가장 가까운 이웃 검색

메모들