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

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 (n⁵) while the execution order of the best available algorithms is O (n¹⁷ poly-logn). Another advantage of this algorithm is the independence of restrictions on simple orthogonal polygons.

Material and methods









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.



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

Partitioning into smaller rectangles, each of which is an r-star polygon.
Updating the range of rectangular guards into the registered guards (in order of their priority).
Reaching the minimum number of guards.

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../files/site1/files/42/1Abstract.pdf