근사 알고리즘 질문, n 포인트에 클러스터링

Question

그래서 내가 생각한 알고리즘은 각 지점에서 공을 중심으로 공을 중심으로 한 점을 가리키는 것과 가장 많은 점을 캡슐화 한 지점을 추적하는 것입니다.그런 다음 발견 된 최대 볼에서 캡슐화 된 점을 제거한 다음 모든 점을 다시 반복합니다.더 이상 캡슐화되지 않은 점이 없을 때까지 계속하십시오.우리가 발견 한 모든 센터를 반환하십시오.

이 알고리즘이 올바른지 확실하지 않습니다.o (1) 근사 알고리즘은 O ( $ \ frac {\ delta_ {ours}} {\ delta} $ )의 관점에서 제공됩니다.요구 사항은 $ n ^ {2} $ 의 순서로 내 것으로 믿는 다항식 알고리즘입니다.

근사 알고리즘의 정확성을 증명하는 방법을 모르겠습니다.

Answer 1

더 간단한 알고리즘 인 욕심 많은 알고리즘이 있습니다. 이 알고리즘은 몇 가지 순서로 점을 반복합니다. 처음에는 센터 세트가 비어 있습니다. $ P $ 이 거리 $ P $ 에 도달하면 컨테이너 "> $ 2 \ Δ $ 선택한 센터 중 하나의 컨테이너> 아무 것도하지 않습니다. 그렇지 않으면 $ P $ 을 센터 세트에 추가합니다. 이 알고리즘의 순진한 구현은 Time $ o (KN) $ , 다항식 인

왜이 일을합니까? $ p_ {i_1}, \ ldots, p_ {i_k} $ \ span class="수학 - 컨테이너"> $ \ Δ $ 의 공이 있다고 가정합니다. $ 전체 세트를 덮고 위의 알고리즘이 $ p_ {j_1}, \ ldots, p_ j_k} $ 을 선택한 것으로 가정합니다. 우리는 세트의 모든 지점이 거리 $ 2 \ Δ $

$ p $ 의 경우 $ c (p) $ 은 < SPAN 클래스="수학 컨테이너"> $ P_ {i_1}, \ ldots, p_ {i_k} $ $ p $ 에 가장 가깝습니다. 나는 $ c (p_ {j_a}) \ Neq C (p_ {j_b}) \ neq c (p_ {j_b}) $ $ a \ neq B $ . 실제로, $ \ | p_ {j_a} -p_ {j_b} \ | > 2 \ 델타 $ . 그러나 $ c (p_ j_a})= C (p_ {j_b})= q $ , $ \ | p_ {j_a} -p_ {j_b} \ | \ leq \ | p_ {j_a} -q \ | + \ | q-p_ {j_b} \ | \ LEQ 2 \ 델타 $ .

$ C (p_a {j_a})= p_ {i_a} $ 을 사용하여 임의의 포인트 $ P $ 세트에서. $ c (p)= p_ {i_a} $ 이라고 가정 해보십시오. 그런 다음 $ \ | P-P_ {J_A} \ | \ leq \ | p-p_ {i_a} \ | + \ | p_ {i_a} -p_ {j_a} \ | \ LEQ 2 \ 델타 $ .