تفکیکپذیری نقاط رنگی با اشکال هندسی یکی از مسایل مطرح در هندسه محاسباتی است که کاربردهایی از جمله در یادگیری ماشین و شناسایی الگو دارد. در این مسأله دو سری نقطه P و Q به ترتیب به رنگهای قرمز و آبی و به اندازه n در صفحه داده شده است. حال لازم است یک شکل هندسی مشخص را ب چکیده کامل
تفکیکپذیری نقاط رنگی با اشکال هندسی یکی از مسایل مطرح در هندسه محاسباتی است که کاربردهایی از جمله در یادگیری ماشین و شناسایی الگو دارد. در این مسأله دو سری نقطه P و Q به ترتیب به رنگهای قرمز و آبی و به اندازه n در صفحه داده شده است. حال لازم است یک شکل هندسی مشخص را به گونهای در صفحه قرار دهیم که کلیه نقاط آبی را در برگرفته و شامل هیچ نقطه قرمزی نباشد. در کارهای پیشین الگوریتمهایی برای تفکیکپذیری نقاط با گوه و مستطیل ارائه گردیده ولی تا به حال الگوریتمی برای تفکیکپذیری نقاط با یک مثلث و همچنین مثلثی که یک زاویه آن مشخص باشد (مثلاً قائمالزاویه) ارائه نشده است. در این مقاله الگوریتمی جدید و کارا برای تفکیکپذیری نقاط رنگی با مثلث قائمالزاویه ارائه میکنیم که قادر خواهد بود با استفاده از راهکار خط جاورب چرخشی، معرفی رخدادها و پردازش آنها در زمان کارای O(nlogn) کلیه مثلثهای قائمالزاویه تفکیککننده را گزارش کند.
پرونده مقاله
خوشهبندی یکی از تکنیکهای مهم کشف دانش در پایگاه دادههای مکانی است. الگوریتمهای خوشهبندی مبتنی بر چگالی یکی از روشهای اصلی برای خوشهبندی در دادهکاوی هستند. الگوریتم DBSCAN پایه روشهای خوشهبندی مبتنی بر چگالی است که علیرغم مزایایی که دارد دارای مشکلاتی نظیر سخت چکیده کامل
خوشهبندی یکی از تکنیکهای مهم کشف دانش در پایگاه دادههای مکانی است. الگوریتمهای خوشهبندی مبتنی بر چگالی یکی از روشهای اصلی برای خوشهبندی در دادهکاوی هستند. الگوریتم DBSCAN پایه روشهای خوشهبندی مبتنی بر چگالی است که علیرغم مزایایی که دارد دارای مشکلاتی نظیر سختبودن تعیین پارامترهای ورودی و عدم توانایی کشف خوشههای با چگالی متفاوت نیز است.
در این مقاله الگوریتمی ارائه شده که برخلاف الگوریتم DBSCAN، قابلیت تشخیص خوشههای با چگالی متفاوت را دارد. این الگوریتم همچنین خوشههای تودرتو و چسبیده به هم را نیز به خوبی تشخیص میدهد. ایده الگوریتم پیشنهادی به این صورت است که ابتدا با استفاده از تکنیکی چگالیهای مختلف مجموعه داده را تشخیص داده و برای هر چگالی یک شعاع Eps تعیین میکند. سپس الگوریتم DBSCAN جهت اعمال بر روی مجموعه داده، با پارامترهای به دست آمده تطبیق داده میشود. الگوریتم پیشنهادی بر روی مجموعه دادههای استاندارد و مصنوعی تست شده است و نتایج به دست آمده با نتایج حاصل از الگوریتم DBSCAN و پنج بهبود الگوریتم DBSCAN شامل: VDBSCAN، VMDBSCAN، LDBSCAN، DVBSCAN و MDDBSCAN که همگی برای رفع مشکل تغییرات چگالی الگوریتم DBSCAN ارائه شدهاند، بر اساس معیارهای ارزیابی روشهای خوشهبندی مقایسه شدهاند. نتایج ارزیابیها نشان میدهد که الگوریتم پیشنهادی از دقت بالا و درصد خطای پایینی برخوردار بوده و نتایج بهتری نسبت به سایر الگوریتمها داشته است.
پرونده مقاله
مسئله پوشش از مسایل مهم و پرکاربرد در هندسه محاسباتي است که در اين مسأله، نقاط بايستي با حداقل يک شکل هندسي پوشانده شوند. نوع خاصي از مسأله پوشش، مسئله جداسازي نقاط است که در اين مسئله حداقل دو دسته نقطه وجود دارد که تمايز آنها با رنگ نشان داده ميشود (براي مثال نقاط آب چکیده کامل
مسئله پوشش از مسایل مهم و پرکاربرد در هندسه محاسباتي است که در اين مسأله، نقاط بايستي با حداقل يک شکل هندسي پوشانده شوند. نوع خاصي از مسأله پوشش، مسئله جداسازي نقاط است که در اين مسئله حداقل دو دسته نقطه وجود دارد که تمايز آنها با رنگ نشان داده ميشود (براي مثال نقاط آبي و قرمز) و بايستي نقاط با يک شکل هندسي از هم جدا شوند که به اين شکل هندسي، جداکننده ميگويند. در اين مقاله مسئله جداسازي نقاط آبي و قرمز با دو- گوه جداکننده با زاويه مشخص مورد بررسي قرار ميگيرد. الگوريتم ارائهشده براي اين مسأله تمام دو- گوههاي جداکننده با زاويه مشخص را در زمان بهينه O (n log n) گزارش ميکند.
پرونده مقاله