دوره 4، شماره 2 - ( پاییز و زمستان 1397 )                   دوره 4 شماره 2 صفحات 132-115 | برگشت به فهرست نسخه ها


XML English Abstract Print


Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:

Borna K. A Fast Algorithm for Covering Rectangular Orthogonal Polygons with a Minimum Number of r-Stars. mmr 2018; 4 (2) :115-132
URL: http://mmr.khu.ac.ir/article-1-2680-fa.html
برنا کیوان. الگوریتمی سریع برای پوشش دید مستطیلی چندضلعی های متعامد ساده با حداقل تعداد r-Star ها . پژوهش های ریاضی. 1397; 4 (2) :115-132

URL: http://mmr.khu.ac.ir/article-1-2680-fa.html


دانشگاه خوارزمی، دانشکده علوم ریاضی و کامپیوتر ، keivan.borna@gmail.com
چکیده:   (3492 مشاهده)
این مقاله الگوریتمی برای پوشش دید چندضلعی‌های متعامد ساده با حداقل تعداد نگهبانان به‌دست می‌دهد. در واقع حداقل تعداد نگهبان را برای چندضلعی‌های ساده (بدون حفره) متعامد برای همۀ حالت‌ها بررسی کرده و قادر هستیم که برای هر یک از نگهبانان نیز محدودۀ مستطیل شکلی را بیابیم. به‌عبارت دیگر مسئلۀ پوشش چندضلعی‌های متعامد ساده با حداقل r-Star ها را بررسی می‌کنیم. در هر چندضلعی متعامد P دو نقطۀ p و q ، نسبت به‌هم r-visible هستند اگر و تنها اگر آن دو نقطه را دو گوشه مخالف مستطیلی در نظر بگیریم، تمام مستطیل درون چندضلعی P  قرار داشته باشد. حال یک چندضلعی P را یک r-Star گوییم اگر یک نقطۀ p در آن وجود داشته باشد به‌طوری‌که هر نقطۀ q عضو چندضلعی، ازp ، r-visible باشد. در این مقاله الگوریتمی را پیشنهاد می‌کنیم که روی همۀ چندضلعی‌های ساده متعامد کاربرد دارد و قادر است حداقل تعداد نگهبانان را در جای خود مستقر کند. این الگوریتم با استفاده از روشی به‌نام مستطیل‌بندی (تقسیم چندضلعی متعامد به تعدادی مستطیل)، تعدادی از r-Star ها را افراز کرده و به پردازش آن‌ها برای درج نگهبانان در محل خود برای رسیدن به هدف، که حداقل تعداد نگهبانان است می‌پردازد. الگوریتم پیشنهادی ما قادر است تا در زمان  حداقل تعداد نگهبانان را به‌همراه محدوده مستطیل شکلی برای آن‌ها تعیین کند در حالی‌که مرتبۀ اجرایی بهترین الگوریتم‌های موجود قبلی   بوده است. از دیگر مزایای این الگوریتم می‌‌توان به نداشتن محدودیت در چندضلعی های متعامد ساده اشاره کرد.
متن کامل [PDF 625 kb]   (596 دریافت)    
نوع مطالعه: علمی پژوهشی بنیادی | موضوع مقاله: جبر
دریافت: 1396/6/31 | ویرایش نهایی: 1397/10/24 | پذیرش: 1396/11/30 | انتشار: 1397/10/24 | انتشار الکترونیک: 1397/10/24

ارسال نظر درباره این مقاله : نام کاربری یا پست الکترونیک شما:
CAPTCHA

ارسال پیام به نویسنده مسئول


بازنشر اطلاعات
Creative Commons License این مقاله تحت شرایط Creative Commons Attribution-NonCommercial 4.0 International License قابل بازنشر است.

کلیه حقوق این وب سایت متعلق به پژوهش‌های ریاضی می باشد.

طراحی و برنامه نویسی : یکتاوب افزار شرق

© 2024 CC BY-NC 4.0 | Mathematical Researches

Designed & Developed by : Yektaweb