A Heuristic Algorithm For The Art Gallery Guard Problems

The art gallery problem origins from real life, it has attracted more and more researchers. Nowadays, it has very important application in many domains. Because the computation of g(P_n) is an NP-hard problem, Many researchers try to present somenear-optimal algorithms for the art gallery guard problems. The paper proposes a heuristic algorithm which solve the number of guards for the most of polygons with k reflex vertices, In general case, the number is superior to k guards. Thus, whether in theory or practical application, it has importance and significance.There are two mainly works in this paper:Firstly, the art gallery theorem shows that the minimum number of guard is [n/3]for polygons. Concave vertices have special role when research the number of guards of polygons. Because k guards is are not optimal for the most of polygons with k reflex vertices. Based on the reflex vertices, this paper puts forward subdivision and its algorithm by analyzing the simple polygons subdivision and algorithm, and obtains a conclusion the number of guards for most simple polygon with k reflex vertex is G,which [k/2]≤G≤k.Secondly, in the orthogonal art gallery problem for guard, Kahn, klawe and Kleitman put forward a conclusion: For arbitrary even numbers n , n≥4 we have g_⊥(n) = [n/4] . According to the property that any orthogonal polygon is convexquadrilaterizable, obtaining a special triangulation about orthogonal polygon, then, analyzing the adjacent relation between the two adjacent triangles in the triangulation, and using a sort 4- coloring, presenting a new proof for orthogonal art gallery theorem.