Dominating sets of agents in visibility graphs: distributed algorithms for art gallery problems

Abstract

The Art Gallery Problem asks to find a minimum subset of vertices in a polygon that are sufficient to observe the interior. This problem arises in a variety of multiagent systems, including robotics, sensor networks, wireless networking, and surveillance. Despite the fact that the centralized version of the problem has been extensively studied for the past thirty years, there is relatively little in the literature describing distributed solutions to the problem that have desirable guarantees in both runtime and optimality. We propose and analyze a new distributed algorithm for approximating a solution to this problem and a number of its variants that runs in a linear number of communication rounds with respect to the number of nodes (independent of the topology of the network), and, under assumptions on the embedding of the edge weights, will run in a logarithmic number of communication rounds producing solutions within a constant factor of optimal.