دوره 4، شماره 2 - ( پاییز و زمستان 1397 )
دوره 4 شماره 2 صفحات 132-115 |
برگشت به فهرست نسخه ها
دانشگاه خوارزمی، دانشکده علوم ریاضی و کامپیوتر ، keivan.borna@gmail.com
چکیده: (4229 مشاهده)
این مقاله الگوریتمی برای پوشش دید چندضلعی‌های متعامد ساده با حداقل تعداد نگهبانان به‌دست می‌دهد. در واقع حداقل تعداد نگهبان را برای چندضلعی‌های ساده (بدون حفره) متعامد برای همۀ حالت‌ها بررسی کرده و قادر هستیم که برای هر یک از نگهبانان نیز محدودۀ مستطیل شکلی را بیابیم. به‌عبارت دیگر مسئلۀ پوشش چندضلعی‌های متعامد ساده با حداقل r-Star ها را بررسی می‌کنیم. در هر چندضلعی متعامد P دو نقطۀ p و q ، نسبت به‌هم r-visible هستند اگر و تنها اگر آن دو نقطه را دو گوشه مخالف مستطیلی در نظر بگیریم، تمام مستطیل درون چندضلعی P قرار داشته باشد. حال یک چندضلعی P را یک r-Star گوییم اگر یک نقطۀ p در آن وجود داشته باشد به‌طوری‌که هر نقطۀ q عضو چندضلعی، ازp ، r-visible باشد. در این مقاله الگوریتمی را پیشنهاد می‌کنیم که روی همۀ چندضلعی‌های ساده متعامد کاربرد دارد و قادر است حداقل تعداد نگهبانان را در جای خود مستقر کند. این الگوریتم با استفاده از روشی به‌نام مستطیل‌بندی (تقسیم چندضلعی متعامد به تعدادی مستطیل)، تعدادی از r-Star ها را افراز کرده و به پردازش آن‌ها برای درج نگهبانان در محل خود برای رسیدن به هدف، که حداقل تعداد نگهبانان است می‌پردازد. الگوریتم پیشنهادی ما قادر است تا در زمان حداقل تعداد نگهبانان را به‌همراه محدوده مستطیل شکلی برای آن‌ها تعیین کند در حالی‌که مرتبۀ اجرایی بهترین الگوریتم‌های موجود قبلی بوده است. از دیگر مزایای این الگوریتم می‌‌توان به نداشتن محدودیت در چندضلعی های متعامد ساده اشاره کرد.
واژه‌های کلیدی: چندضلعی متعامد (راست گوشه)، مستطیل‌بندی، r-Star، r-visible، افراز r-Star ها. رده بندی موضوعی: 52B55، 68U05.
نوع مطالعه: علمی پژوهشی بنیادی |
موضوع مقاله:
جبر
دریافت: 1396/6/31 | ویرایش نهایی: 1397/10/24 | پذیرش: 1396/11/30 | انتشار: 1397/10/24 | انتشار الکترونیک: 1397/10/24
دریافت: 1396/6/31 | ویرایش نهایی: 1397/10/24 | پذیرش: 1396/11/30 | انتشار: 1397/10/24 | انتشار الکترونیک: 1397/10/24
| بازنشر اطلاعات | |
 |
این مقاله تحت شرایط Creative Commons Attribution-NonCommercial 4.0 International License قابل بازنشر است. |