TR-114: An Optimal Algorithm for Detecting Weak Visibility of a Polygon

Abstract

In 1981, Avis and Toussaint gave a linear-time algorithm for the following problem: Given a simple n-vertex polygon P and an edge of P, determine whether each point in P can be seen by some (not necessarily the same) point on the edge. They posed the more general problem of finding a sub-quadratic algorithm for determining whether such an edge exists. In this paper, we present a linear-time algorithm for determining all (if any) such edges of a given simple polygon.