عدد ‎$k$‎ همراه با ‎$n$‎ نقطه با مختصات صحیح داده شده‌اند که قدر مطلق مختصّات این نقاط از ‎$n$‎ کمتر است. می‌خواهیم تعدادی مستطیل با مساحت حداکثر ‎$k$‎ و با اضلاع موازی محورهای مختصّات در صفحه قرار دهیم به طوری که تمام این ‎$n$‎ نقطه را بپوشانند(‎یک نقطه پوشانیده می‌شود اگر و فقط اگر درون حداقل یک مستطیل قرار بگیرد).

علیرضا توانسته با استفاده از ‎$x$‎ مستطیل همه‌ی نقاط را بپوشاند. ما هم برای پوشاندن نقاط روش زیر را انتخاب می‌کنیم:

در هر لحظه مستطیلی با شرایط مسئله را انتخاب می‌کنیم که بیشترین تعداد نقاطی را که تاکنون پوشیده نشده‌اند را بپوشاند. این کار را تا زمانی که نقطه‌ی پوشیده نشده‌ای وجود دارد ادامه می‌دهیم.

اگر تعداد نقاط پوشیده نشده قبل از انتخاب مستطیل ‎$i$‎ام را ‎$a_i$‎ بنامیم؛

1. ثابت کنید که تعداد نقاطی که در مرحله‌ی ‎$i$‎ام به نقاط پوشیده شده اضافه می‌شوند لااقل ‎$a_i \over x$‎ است.
2. ثابت کنید که پس از ‎$x$‎ مرحله انتخاب مستطیل تعداد نقاط انتخاب نشده حداکثر ‎$n \over 2$‎ می‌باشد.
3. ثابت کنید الگوریتم ما از حداکثر ‎$x\lg(n)$‎ مستطیل برای پوشاندن کل نقاط استفاده می‌کند.

• سوال بعد
• سوال قبل