5 SID.ir | الگوريتمي سريع براي پوشش ديد مستطيلي چندضلعي هاي متعامد ساده با حداقل تعداد r-Star ها

مشخصات مقاله

 
عنوان مقاله: 

الگوريتمي سريع براي پوشش ديد مستطيلي چندضلعي هاي متعامد ساده با حداقل تعداد r-Star ها

 
نویسندگان: 
 
آدرس:  
* دانشگاه خوارزمی، دانشکده علوم ریاضی و کامپیوتر
 
چکیده: 
اين مقاله الگوريتمي براي پوشش ديد چندضلعي هاي متعامد ساده با حداقل تعداد نگهبانان به دست مي دهد. در واقع حداقل تعداد نگهبان را براي چندضلعي هاي ساده (بدون حفره) متعامد براي همه ي حالت ها بررسي کرده و قادر هستيم که براي هر يک از نگهبانان نيز محدوده ي مستطيل شکلي را بيابيم. به عبارت ديگر مسئله ي پوشش چندضلعي هاي متعامد ساده با حداقل r-Star ها را بررسي مي کنيم. در هر چندضلعي متعامد P دو نقطه ي p و q، نسبت به هم r-visible هستند اگر و تنها اگر آن دو نقطه را دو گوشه مخالف مستطيلي در نظر بگيريم، تمام مستطيل درون چندضلعي P قرار داشته باشد. حال يک چندضلعي P را يک r-Star گوييم اگر يک نقطه ي p در آن وجود داشته باشد به طوري که هر نقطه ي q عضو چندضلعي، ازp، r-visible باشد. در اين مقاله الگوريتمي را پيشنهاد مي کنيم که روي همه ي چندضلعي هاي ساده متعامد کاربرد دارد و قادر است حداقل تعداد نگهبانان را در جاي خود مستقر کند. اين الگوريتم با استفاده از روشي به نام مستطيل بندي (تقسيم چندضلعي متعامد به تعدادي مستطيل)، تعدادي از r-Star ها را افراز کرده و به پردازش آن ها براي درج نگهبانان در محل خود براي رسيدن به هدف، که حداقل تعداد نگهبانان است مي پردازد. الگوريتم پيشنهادي ما قادر است تا در زمان حداقل تعداد نگهبانان را به همراه محدوده مستطيل شکلي براي آن ها تعيين کند در حالي که مرتبه ي اجرايي بهترين الگوريتم هاي موجود قبلي بوده است. از ديگر مزاياي اين الگوريتم مي توان به نداشتن محدوديت در چندضلعي هاي متعامد ساده اشاره کرد.
 
کلید واژه: 

 
موضوعات مرتبط: 
-
 
ارجاعات: 
  • ندارد
 
 
مقالات نشریه ای مرتبط: 
  • ندارد
 
مقالات همایشی مرتبط: 
  • ندارد
 

  چکیده انگلیسی بازدید یکساله 31
 
 
آخرین های بلاگ
ورود به بلاگ مرکز اطلاعات علمی