Mathematical Researches

fa الگوریتمی سریع برای پوشش دید مستطیلی چندضلعی های متعامد ساده با حداقل تعداد r-Star ها A Fast Algorithm for Covering Rectangular Orthogonal Polygons with a Minimum Number of r-Stars جبر alg علمی پژوهشی بنیادی S این مقاله الگوریتمی برای پوشش دید چندضلعی‌های متعامد ساده با حداقل تعداد نگهبانان به‌دست می‌دهد. در واقع حداقل تعداد نگهبان را برای چندضلعی‌های ساده (بدون حفره) متعامد برای همۀ حالت‌ها بررسی کرده و قادر هستیم که برای هر یک از نگهبانان نیز محدودۀ مستطیل شکلی را بیابیم. به‌عبارت دیگر مسئلۀ پوشش چندضلعی‌های متعامد ساده با حداقل r-Star ها را بررسی می‌کنیم. در هر چندضلعی متعامد P دو نقطۀ p و q ، نسبت به‌هم r-visible هستند اگر و تنها اگر آن دو نقطه را دو گوشه مخالف مستطیلی در نظر بگیریم، تمام مستطیل درون چندضلعی P  قرار داشته باشد. حال یک چندضلعی P را یک r-Star گوییم اگر یک نقطۀ p در آن وجود داشته باشد به‌طوری‌که هر نقطۀ q عضو چندضلعی، ازp ، r-visible باشد. در این مقاله الگوریتمی را پیشنهاد می‌کنیم که روی همۀ چندضلعی‌های ساده متعامد کاربرد دارد و قادر است حداقل تعداد نگهبانان را در جای خود مستقر کند. این الگوریتم با استفاده از روشی به‌نام مستطیل‌بندی (تقسیم چندضلعی متعامد به تعدادی مستطیل)، تعدادی از r-Star ها را افراز کرده و به پردازش آن‌ها برای درج نگهبانان در محل خود برای رسیدن به هدف، که حداقل تعداد نگهبانان است می‌پردازد. الگوریتم پیشنهادی ما قادر است تا در زمان  حداقل تعداد نگهبانان را به‌همراه محدوده مستطیل شکلی برای آن‌ها تعیین کند در حالی‌که مرتبۀ اجرایی بهترین الگوریتم‌های موجود قبلی   بوده است. از دیگر مزایای این الگوریتم می‌‌توان به نداشتن محدودیت در چندضلعی های متعامد ساده اشاره کرد. Introduction 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. Material and methods   <table cellpadding="0" cellspacing="0"> <tbody> <tr> <td height="0"></td> </tr> <tr> <td></td> <td>Our processing is based on orthogonal or right-angled polygons, so we only have four types of edges. The northern edge, or N, the southern edge or S, the eastern edge or E, the western edge or W-edge. If the interior of polygon lies below/above/left/right of an edge, respectively, then that edge is called N/S/E/W, respectively. There are also four types of dents, including North Dent (N-dent), Southern Dent (S-dent), Eastern Dent (E-dent) and Western Dent (W-dent); see Figure 1.</td> </tr> </tbody> </table> Figure 1. A simple orthogonal polygon with a variety of edges and dents In our proposed algorithm, after rectangles, new edges and vertices are created in the orthogonal polygon P, which we call the sub-edges and sub-vertices. Sub-vertices are known as horizontal and vertical edges, and are formed from the intersection of the adjacent edges with the main or minor edges. The orthogonal polygons can be classified into class-k, such that 1≤k≤4, according to the type of dents which is defined so that its intersections are at most k different directions. Class-2 polygons can be re-categorized into classes 2a, so that 2 directions are parallel to the dents (i.e., N and S or E and W) and Class 2b so that 2 directions are perpendicular to each other. The field of view of the guards or a rectangular field of view is defined as r-visibility. In each orthogonal polygon P, two opposite-corner situated points p and q are called r-visible to each other if the entire rectangle containing them is within P. Now we consider 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 the r-Star problem, we assume that each guard has a 360-degree field of view. Results and discussion In this paper, a new idea is proposed based on the rectangular orthogonal polygon, which creates new edges. In fact, the original orthogonal polygon P with a rectangular method will be divided into a number of rectangles, so that their geometric communities are exactly the same as P. Then the edges are placed in the two groups of main and minor edges. Obviously, the shared edges between the two rectangles are minor and will not prevent the guard from seeing. Therefore, the primary polygon is decomposed into rectangles and then, according to the orthogonal polygon partition method, P is divided into two or more orthogonal polygons, if possible. We make each one of them an r-Star. Then set the deadlock rectangles and set up an incremental guard in each range for each of them. In the next step, we start from the top r-Star with a sweep-line method and check the inserted guards and, if necessary, r-stars and guard rectangles are requested by our Rectangular Guards method. We will continue to work and expand the first r-Star as far as possible, and will do so for the rest of the r-stars, so that the minimum number of guards or let's say the least number of r-stars are obtained. In this article, we are actually looking for the minimum number of r-stars. The steps of our novel algorithm are as follows: 1. Partitioning into rectangles 2. Partitioning the output of Step 1 into orthogonal r-Stars. 3. Determining the guards for the output of Step 2. 4. Scrolling among the r-stars and setting the minimum number of guards 5. Allocating guards for parent, child and minor r-Stars. Conclusion       We considered the problem of covering simple orthogonal polygons with no restrictions on the type and number of dents. This algorithm is capable of <ul> <li>Partitioning into smaller rectangles, each of which is an r-star polygon.</li> <li>Updating the range of rectangular guards into the registered guards (in order of their priority).</li> <li>Reaching the minimum number of guards.</li> </ul>  In this paper, the idea was presented on simple orthogonal polygons that do not have a hole. This paper also paves the way for working on other types of polygons that have cavities. In fact, holes can be seen as columns in the gallery, which can also be considered as simple orthogonal rectangles or polygons. The problem here is that these rectangles are different with the rectangles in the polygon that are presented in this article and prevent the guards from seeing.<a href="./files/site1/files/42/1Abstract.pdf">./files/site1/files/42/1Abstract.pdf</a> چندضلعی متعامد (راست گوشه), مستطیل‌بندی, r-Star , r-visible , افراز r-Star ها. رده بندی موضوعی: 52B55, 68U05. Orthogonal polygon (right corner), rectangles, r-Star, r-visible, r-stars partition. 115 132 http://mmr.khu.ac.ir/browse.php?a_code=A-10-299-1&slc_lang=fa&sid=1 Keivan Borna کیوان برنا keivan.borna@gmail.com 10031947532846002299 10031947532846002299 Yes Kharazmi University دانشگاه خوارزمی، دانشکده علوم ریاضی و کامپیوتر