Generalizing the Covering Path Problem on a Grid

Abstract

We study the covering path problem on a grid of R^{2}. We generalize earlier results on a rectangular grid and prove that the covering path cost can be bounded by the area and perimeter of the grid. We provide (2+ε) and (1+ε)-approximations for the problem on a general grid and on a convex grid, respectively.