====== افراز $k$-تایی ======


$n$ نقطه‌ی $p_n,…,p_2,p_1$ در فضای ۳ بعدی  داده شده است. یک افراز  $k$-تایی، تقسیم‌بندی این نقاط به $k$ دسته $A_k,…,A_2,A_1$ است، به طوری که هر نقطه دقیقا در یکی از $A_i$ها آمده باشد.

قطر یک دسته برابر بیش‌ترین فاصله‌ی دو نقطه در آن دسته می‌باشد. اندازه‌ی یک افراز نیز برابر بیشینه‌ی قطر دسته‌هایش تعریف می‌شود. $OPT$ مقدار کمینه‌ی اندازه‌ی یک افراز است.

الگوریتم زیر را در نظر بگیرید:
  - $S=\{ \{p_1\} , \{p_2 \} , …. , \{p_k \} \}$ و $i=k$
  - $i=i+1$
  - $S=S\cup \{ \{p_i\} \}$
  - از هر یک از $k+1$ مجموعه‌ی درون مجموعه‌ی درون $S$ یک نقطه به عنوان نماینده انتخاب کن و دو نماینده‌ای که فاصله‌شان از فاصله‌ی هر دو نماینده‌ای کم‌تر مساوی است را در نظر بگیر. مجموعه‌های مربوط به این دو نماینده را با هم ادغام کن.( پس اکنون $k$ مجموعه درون $S$ وجود دارد.)
  - اگر $i<n$ بود به ۲ برو وگرنه تمام.


در پایان الگوریتم $k$ مجموعه از نقاط خواهیم داشت که در واقع یک افراز $k$-تایی است. ثابت کنید اندازه‌ی این افراز از $(2k-1)\times OPT$ بیش‌تر نیست.


  * [[سوال ۳|سوال قبل]]