الگوریتمی سریع برای پوشش دید مستطیلی چندضلعی های متعامد ساده با حداقل تعداد r-star ها
|
|
|
|
|
|
|
|
نویسنده
|
برنا کیوان
|
|
منبع
|
پژوهش هاي رياضي - 1397 - دوره : 4 - شماره : 2 - صفحه:115 -132
|
|
چکیده
|
این مقاله الگوریتمی برای پوشش دید چندضلعی‌های متعامد ساده با حداقل تعداد نگهبانان به‌دست می‌دهد. در واقع حداقل تعداد نگهبان را برای چندضلعی‌های ساده (بدون حفره) متعامد برای همۀ حالت‌ها بررسی کرده و قادر هستیم که برای هر یک از نگهبانان نیز محدودۀ مستطیل شکلی را بیابیم. به‌عبارت دیگر مسئلۀ پوشش چندضلعی‌های متعامد ساده با حداقل rstar ها را بررسی می‌کنیم. در هر چندضلعی متعامد p دو نقطۀ p و q ، نسبت به‌هم rvisible هستند اگر و تنها اگر آن دو نقطه را دو گوشه مخالف مستطیلی در نظر بگیریم، تمام مستطیل درون چندضلعی p قرار داشته باشد. حال یک چندضلعی p را یک rstar گوییم اگر یک نقطۀ p در آن وجود داشته باشد به‌طوری‌که هر نقطۀ q عضو چندضلعی، ازp ، rvisible باشد. در این مقاله الگوریتمی را پیشنهاد می‌کنیم که روی همۀ چندضلعی‌های ساده متعامد کاربرد دارد و قادر است حداقل تعداد نگهبانان را در جای خود مستقر کند. این الگوریتم با استفاده از روشی به‌نام مستطیل‌بندی (تقسیم چندضلعی متعامد به تعدادی مستطیل)، تعدادی از rstar ها را افراز کرده و به پردازش آن‌ها برای درج نگهبانان در محل خود برای رسیدن به هدف، که حداقل تعداد نگهبانان است می‌پردازد. الگوریتم پیشنهادی ما قادر است تا در زمان حداقل تعداد نگهبانان را به‌همراه محدوده مستطیل شکلی برای آن‌ها تعیین کند در حالی‌که مرتبۀ اجرایی بهترین الگوریتم‌های موجود قبلی بوده است. از دیگر مزایای این الگوریتم می‌‌توان به نداشتن محدودیت در چندضلعی های متعامد ساده اشاره کرد.
|
|
کلیدواژه
|
چندضلعی متعامد (راست گوشه)، مستطیل‌بندی، افراز r-star ها. رده بندی موضوعی: 52b55،
|
|
آدرس
|
دانشگاه خوارزمی, دانشکده علوم ریاضی و کامپیوتر, ایران
|
|
پست الکترونیکی
|
borna@khu.ac.ir
|
|
|
|
|
|
|