جداسازی نقاط دو رنگ با دو- گوه با زاویه مشخص
الموضوعات : electrical and computer engineeringمریم ملکی شهرکی 1 , علیرضا باقری 2 , مهدیس نیری 3
1 - دانشگاه آزاد اسلامی واحد تهران شمال
2 - دانشگاه صنعتی امیرکبیر
3 - دانشگاه آزاد اسلامی واحد تهران شمال
الکلمات المفتاحية: هندسه محاسباتي پوشش جداسازي دو- گوه الگوريتم نقاط دو رنگ,
ملخص المقالة :
مسئله پوشش از مسایل مهم و پرکاربرد در هندسه محاسباتي است که در اين مسأله، نقاط بايستي با حداقل يک شکل هندسي پوشانده شوند. نوع خاصي از مسأله پوشش، مسئله جداسازي نقاط است که در اين مسئله حداقل دو دسته نقطه وجود دارد که تمايز آنها با رنگ نشان داده ميشود (براي مثال نقاط آبي و قرمز) و بايستي نقاط با يک شکل هندسي از هم جدا شوند که به اين شکل هندسي، جداکننده ميگويند. در اين مقاله مسئله جداسازي نقاط آبي و قرمز با دو- گوه جداکننده با زاويه مشخص مورد بررسي قرار ميگيرد. الگوريتم ارائهشده براي اين مسأله تمام دو- گوههاي جداکننده با زاويه مشخص را در زمان بهينه O (n log n) گزارش ميکند.
