تفکیکپذیری نقاط رنگی با اشکال هندسی یکی از مسایل مطرح در هندسه محاسباتی است که کاربردهایی از جمله در یادگیری ماشین و شناسایی الگو دارد. در این مسأله دو سری نقطه P و Q به ترتیب به رنگهای قرمز و آبی و به اندازه n در صفحه داده شده است. حال لازم است یک شکل هندسی مشخص را ب چکیده کامل
تفکیکپذیری نقاط رنگی با اشکال هندسی یکی از مسایل مطرح در هندسه محاسباتی است که کاربردهایی از جمله در یادگیری ماشین و شناسایی الگو دارد. در این مسأله دو سری نقطه P و Q به ترتیب به رنگهای قرمز و آبی و به اندازه n در صفحه داده شده است. حال لازم است یک شکل هندسی مشخص را به گونهای در صفحه قرار دهیم که کلیه نقاط آبی را در برگرفته و شامل هیچ نقطه قرمزی نباشد. در کارهای پیشین الگوریتمهایی برای تفکیکپذیری نقاط با گوه و مستطیل ارائه گردیده ولی تا به حال الگوریتمی برای تفکیکپذیری نقاط با یک مثلث و همچنین مثلثی که یک زاویه آن مشخص باشد (مثلاً قائمالزاویه) ارائه نشده است. در این مقاله الگوریتمی جدید و کارا برای تفکیکپذیری نقاط رنگی با مثلث قائمالزاویه ارائه میکنیم که قادر خواهد بود با استفاده از راهکار خط جاورب چرخشی، معرفی رخدادها و پردازش آنها در زمان کارای O(nlogn) کلیه مثلثهای قائمالزاویه تفکیککننده را گزارش کند.
پرونده مقاله