In this paper we focus on approximate solutions to solve a new class of Art Gallery Problems inspired by wireless localization. Instead of the usual guards we consider wireless devices whose signal can cross a certain number, k, of walls. These devices are called k-transmitters. We propose an algorithm for constructing the visibility region of a k-transmitter located on a point of a simple polygon. Then we apply a hybrid metaheuristic strategy to tackle the problem of minimizing the number of k-transmitters, located at vertices, that cover a given simple polygon, and compare its performance with two pure metaheuristics. We conclude that the approximate solutions obtained with the hybrid strategy, for 2-transmitters and 4-transmitters, on simple polygons, monotone polygons, orthogonal polygons and monotone orthogonal polygons, are better than the solutions obtained with the pure strategies.

computational geometry, art gallery problems, visibility and coverage problems, hybrid metaheuristics and approximation algorithms