n نقطهی pn,…,p2,p1 در فضای ۳ بعدی داده شده است. یک افراز k-تایی، تقسیمبندی این نقاط به k دسته Ak,…,A2,A1 است، به طوری که هر نقطه دقیقا در یکی از Aiها آمده باشد.
قطر یک دسته برابر بیشترین فاصلهی دو نقطه در آن دسته میباشد. اندازهی یک افراز نیز برابر بیشینهی قطر دستههایش تعریف میشود. OPT مقدار کمینهی اندازهی یک افراز است.
الگوریتم زیر را در نظر بگیرید:
در پایان الگوریتم k مجموعه از نقاط خواهیم داشت که در واقع یک افراز k-تایی است. ثابت کنید اندازهی این افراز از (2k−1)×OPT بیشتر نیست.