Algorithms for Computing Grazing Area

We consider the problem of sweeping (or grazing) the interior/exterior of a polygon by a flexible rope whose one endpoint (anchor) is attached on the boundary of the polygon. We present a linear-time algorithm to compute the grazing area inside a simple polygon. We show how to extend the algorithm for computing the internal grazing area, without increasing its time complexity, to compute the grazing area in the exterior of a simple polygon. For grazing in the exterior of a convex polygon, we present an \(O(n)\) time algorithm to locate the anchor point that maximizes the simple grazing area. All three algorithms are optimal within a constant factor. Grazing area problems can be viewed as guard placement problems under \(L\)-visibility.