  In this paper, we revisit the distributed coverage control problem with
multiple robots on both metric graphs and in non-convex continuous
environments. Traditionally, the solutions provided for this problem converge
to a locally optimal solution with no guarantees on the quality of the
solution. We consider sub-additive sensing functions, which capture the
scenarios where sensing an event requires the robot to visit the event
location. For these sensing functions, we provide the first constant factor
approximation algorithms for the distributed coverage problem. The
approximation results require twice the conventional communication range in the
existing coverage algorithms. However, we show through extensive simulation
results that the proposed approximation algorithms outperform several existing
algorithms in convex, non-convex continuous, and discrete environments even
with the conventional communication ranges. Moreover, the proposed algorithms
match the state-of-the-art centralized algorithms in the solution quality.
