جدا کردن نقاط با تعداد مساوی به وسیله‌ی خط

تمرین هندسه محاسباتی سری دوم سوال دوم می‌گفت دو خط متقاطع پیدا کنید که نقاط را به قسمت‌های n/4 نقطه‌ای تقسیم کنند.

من برای این کار از ham sandwich cut استفاده کردم و نصف نقاط را قرمز کردم و نصف دیگر نقاط را آبی کردم و بعد نصف نقاطی که قبلاً قرمز بودند بنفش و نصف دیگرش را سبز کردم. مشابه همین کار را برای نقاط آبی هم انجام می‌دهیم. حالا دوباره ham sandwich cut را به کار می‌بریم و یک خط به دست می‌آید. این خط همان جواب مسأله است.

(در تمرین O(n^2) خواسته بود این O(n) است.)