Weak Visibility and Shortest Paths
Subir Kumar Ghosh · Cambridge University Press eBooks · 2007
Problems and Results The notion of weak visibility of a polygon from a segment was introduced by Avis and Toussaint [42] in the context of the art gallery problem. They considered a variation of the problem when there is only one guard and the guard is permitted to move along an edge of the polygon. They defined visibility from an edge v i v i+1 in a simple polygon P in three different ways. P is said to be completely visible from v i υ i+1 if every point z ∈ P and any point w ∈ v i v i+1 , w and z are visible (Figure 3.1(a)). P is said to be strongly visible from v i v i+1 if there exists a point w ∈ v i v i+1 such that for every point z ∈ P, w and z are visible (Figure 3.1(b)). P is said to be weakly visible from v i v i+1 if each point z ∈ P , there exists a point w ∈ v i v i+1 (depending on z ) such that w and z are visible (Figure 3.1(c)). If P is completely visible from v i v i+1 , the guard can be positioned at any point w on v i v i+1 . In other words, P and the visibility polygon V(w) of P from any point w ∈ v i v i+1 are same. If P is strongly visible from v i v i+1 , there exists at least one point w on v i v i+1 from which the guard can see the entire P , i.e., P = V (w). Finally, if P is weakly visible from v i v i+1 , it is necessary for the guard to patrol along v i v i+1 in order to see the entire P .