{'fraction_non_alphanumeric': 0.024135681669928244, 'fraction_numerical': 0.0136986301369863, 'mean_word_length': 4.517985611510792, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Fast Algorithm for Covering Rectangular Orthogonal Polygons with a Minimum Number of r-Stars

Received: 22 Oct. 2017 Revised: 19 Feb. 2018 Extended Abstract (Paper pages 115-132) 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 5 ) while the execution order of the best available algorithms is O (n 17 poly-logn). Another advantage of this algorithm is the independence of restrictions on simple orthogonal polygons.