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

$n$ نقطه‌ی $p_1$، $p_2$، ...، $p_n$ در فضای ۳ بعدی داده شده است. یک افراز $k$-تایی، تقسیم‌بندی این نقاط به $k$ دسته $A_1$، $A_2$، ...، $A_k$ است، به طوری که هر نقطه دقیقا در یکی از $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$ بیش‌تر نیست.

  * [[سوال ۱۰|سوال بعد]]
  * [[سوال ۸|سوال قبل]]