Characterizing and recognizing LR-visibility polygons

A simple polygon PP is LRLR-visible if there are two points ss, tt on the boundary of PP such that every point on the clockwise boundary of PP from ss to tt is visible from some point of the other boundary of PP from tt to ss and vice versa. We show that PP is not LRLR-visible if and only if it has kk non-redundant components such that each of them exactly intersects with k′k′ other components, where 0≤k′≤k−30≤k′≤k−3. Our characterization is obtained by investigating the structure of the considered non-redundant components and representing it by a set of directed chords of a circle. Furthermore, we develop a simple O(n)O(n) time algorithm for determining whether a given polygon with nn vertices is LRLR-visible as well as for reporting a pair or all pairs (s,t)(s,t) which admit LRLR-visibility. This greatly simplifies the existing algorithm for recognizing LRLR-visibility polygons. Also, our result can be used to simplify the existing solutions of other LRLR-visibility problems.