Can Greedy-like Heuristics Be Useful for Solving the Weighted Orthogonal Art Gallery Problem Under Regular Grid Discretization?

Abstract

In this paper we deal with the Weighted Orthogonal Art Gallery Problem which task is to place guards on some vertices of orthogonal polygon P which cover all points from the polygon, such that the total sum of prices assigned to the chosen vertices is minimal. The problem has applications, for example, in installing cameras at the corners of a building such that any piece of room is covered by at least one of the cameras but the price of installation is the smallest possible. In order to solve the problem, the regular grid discretization of the area of polygon is applied. We propose a novel greedy approach which is based on balancing the trade off between the total sum of guards' costs and the total number of not yet covered points from the discretization. This new approach and an existing greedy algorithm are further hybridized with the Integer Linear programming, which is originally formulated for the well known Minimum Set Cover problem. Our experimental results are conducted on two sets of polygons from the literature: one with small area and the other one with large area. They proved that the proposed greedy methods are able to achieve the optimal solutions in most cases for the class of large-area polygons, while in case of the small area polygons, they achieve solutions of reasonable quality within lower runtime than the exact algorithms.