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

A Fast Algorithm for Covering Rectangular Orthogonal Polygons with a Minimum Number of r-Stars

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

This paper presents an algorithm for covering orthogonal polygons with minimal number of guards. This idea examines the minimum number of guards for orthogonal simple polygons (without holes) for all scenarios and can also find a rectangular area for each guards. We consider the problem of covering orthogonal polygons with a minimum number of r-stars. In each orthogonal polygon P, two points' p and q are called r-visible if these two points are in opposite rectangular corners, then the entire rectangle is placed in P. Now we consider a polygon P to be an r-Star if there is a point p in it so that every point q is r-visible from p. In this paper, we propose an algorithm that applies to all simple orthogonal polygons and is able to locate at least the number of guards. Using a method called a rectangular (orthogonal polygonal division into a number of rectangles), the algorithm separates a number of r-stars and processes them in order to insert guards in their place to reach the target, which has the minimum number of guards. Our proposed algorithm is able to determine the minimum number of guards with a rectangular shape at time O (n5) while the execution order of the best available algorithms is O (n17 poly-logn). Another advantage of this algorithm is the independence of restrictions on simple orthogonal polygons.