Inspection of the exterior of polygons under infinite and limited visibility models
Rafa Absar · eScholarship@McGill (McGill) · 2005
We study the problem of externally guarding or inspecting a polygonal environment with a mobile guard (watchman) in both unlimited and limited visibility models. A survey of the literature on guarding problems is presented for both stationary and mobile guards, as well as for both interior and exterior workspaces. Our research concentrates on the external inspection of a single, convex or simple, polygon. In particular, we study the relationship between the interior angles of convex polygons and the length of an external inspection route under unlimited visibility. We then propose a method for computing the shortest external inspection route for convex polygons under limited visibility, and also an approximate solution for simple polygons. Finally, we present experimental work which was performed on random convex polygons to evaluate the results and validate the findings under both types of visibility assumptions.