An Approximation Algorithm for Clarity Edge Covering Problem

Date Added: Apr 2012
Format: PDF

Clarity edge covering problem is a version of art gallery problem. In this problem the goal is finding the minimum number of guards which covers all edges. Here, meaning of visibility is different from art gallery problem and it is restricted. In this paper, a logarithmic approximation algorithm is presented for vertex guard version. In art gallery problem, one should find the minimum number of guards to patrol interior of a polygon. The guards may be placed inside the polygon or on the boundary, and may be stationary or mobile.