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. The task is to place guards on some vertices of an
orthogonal polygon P, such that the total sum of prices assigned to the chosen vertices is minimal and all points from the polygon P are
covered. The problem has applications in practice, for example, in installing cameras at the corners of a building such that all interior
space is covered by at least one of the cameras but the price of installation is the smallest possible. 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 tradeoff
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 wellknown
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 can 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.