Characterizing LR-visibility polygons and related problems

摘要

A simple polygon P is said to be LR-visibility polygon if there exists two points s and t on the boundary of P such that every point of the clockwise boundary of P from s to t (denoted as L) is visible from some point of the counterclockwise boundary of P from s to t (denoted as R) and vice versa. In this paper we derive properties of shortest paths in LR-visibility polygons and present a characterization of LR visibility polygons in terms of shortest paths between vertices. This characterization suggests a simple algorithm for the following recognition problem. Given a polygon P with distinguished vertices s and t, the problem is to determine whether P is a LR-visibility polygon with respect to s and t. Our algorithm for this problem checks LR-visibility by traversing shortest path trees rooted at s and t in DFS manner and it runs in linear time. Using our characterization of LR-visibility polygons, we show that the shortest path tree rooted at a vertex or a boundary point can be computed in linear time for a class of polygons which contains LR-visibility polygons as a subclass. As a result, this algorithm can be used as a procedure for computing the shortest path tree in our recognition algorithm as well as in the recognition algorithm of Das, Heffernan and Narasimhan. Our algorithm computes the shortest path tree by scanning the boundary of the given polygon and it does not require triangulation as a preprocessing step.