جداسازي نقاط دو رنگ با دو - گوه با زاويه مشخص

مسئله پوشش از مسايل مهم و پركاربرد در هندسه محاسباتي است كه در اين مسأله، نقاط بايستي با حداقل يك شكل هندسي پوشانده شوند. نوع خاصي از مسأله پوشش، مسئله جداسازي نقاط است كه در اين مسئله حداقل دو دسته نقطه وجود دارد كه تمايز آنها با رنگ نشان داده مي‌شود (براي مثال نقاط آبي و قرمز) و بايستي نقاط با يك شكل هندسي از هم جدا شوند كه به اين شكل هندسي، جدا‌كننده مي‌گويند. در اين مقاله مسئله جداسازي نقاط آبي و قرمز با دو گوه جدا‌كننده با زاويه مشخص مورد بررسي قرار مي‌گيرد. الگوريتم ارائه‌شده براي اين مسأله تمام دو - گوه‌هاي جدا‌كننده با زاويه مشخص را در زمان بهينه O (n log n) گزارش مي‌كند.