$n$ نقطهی $p_1$، $p_2$، …، $p_n$ در فضای ۳ بعدی داده شده است. یک افراز $k$-تایی، تقسیمبندی این نقاط به $k$ دسته $A_1$، $A_2$، …، $A_k$ است، به طوری که هر نقطه دقیقا در یکی از $A_i$ ها آمده باشد.
قطر یک دسته برابر بیشترین فاصلهی دو نقطه در آن دسته میباشد. اندازهی یک افراز نیز برابر بیشینهی قطر دستههایش تعریف میشود. $OPT$ مقدار کمینهی اندازهی یک افراز است.
الگوریتم زیر را در نظر بگیرید:
در پایان الگوریتم $k$ مجموعه از نقاط خواهیم داشت که در واقع یک افراز $k$-تایی است. ثابت کنید اندازهی این افراز از $(2k-1)\times OPT$ بیشتر نیست.