A Characterization of Link-2 LR-visibility Polygons with Applications - Discrete and Computational Geometry and Graphs - page 164

Observation 2. Suppose that the backward component of a reflex vertex r is
non-redundant, and the backward (forward) link-2 ray-shooting of r is defined.
Then, no point outside of the backward (forward) link-2 ʱ -component of r is link-
2 visible from Succ ( r ) . Moreover, P ( BB 2( r ) ,BB 1( r )) ( P ( BF 1( r ) ,BF 2( r )) )is
the first boundary chain, immediately after BB 1( r ) ( BF 1( r ) ) anti-clockwise
(clockwise), which is not link-2 visible from Succ ( r ) .

A link-2 component C (it may be an ʱ -or ʲ -component) is said to intersect
with the other C if C and C overlap each other on the boundary of P . We call
the endpoint of a link-2 component C the left endpoint if it is first encountered,
and the other endpoint of C the right endpoint if it is second met, in a clockwise
scan of the boundary of P , starting at a point that is not contained in C .
The similarity between the components and the link-2 ʱ / ʲ -components
(Observations 1 and 2 ) makes it easy to establish a one-to-one correspondence
between the forbidden patterns, for LR -visibility polygons and link-2 LR -visibility
polygons.

Lemma 1. Suppose that the given polygon P is not LR -visible. Then, P is link-
2 LR -visible with respect to two boundary points s and t ifandonlyifeachof
the non-redundant link-2 ʱ -components and ʲ -components contains s or t .

Proof. The necessity follows from the definition of the link-2 ʱ -and ʲ -components
and Observation 2 . Assume now that each of the non-redundant link-2 ʱ -
components and ʲ -components contains s or t , and thus, each link-2 component
contains s or t . A reflex vertex r ,say,onthechain L , cannot block Succ ( r )nor
Pred ( r ) from being seen from any point of R ; otherwise, there exists a link-2 com-
ponent that contains neither s nor t , a contradiction. The lemma thus follows.

Lemma 2. A polygon P is not link-2 LR -visible if it has three disjoint link-2
components.

Proof. It simply follows from Lemma 1 , see Fig. 3 (a).

Lemma 3. A polygon P is not link-2 LR -visible if it has k non-redundant link-2
components (they may be the ʱ -or ʲ -components) such that each of them exactly
intersects k other components, where k

5 and k ≤

≥ k − 3 .

Proof. Figure 3 (b) shows an example in which P has five link-2 components; each
of them exactly intersects other three components. As in the proof of Lemma 2
of [ 14 ], we first transform the k non-redundant link-2 components into k directed
chords of a circle R such that the order of chord's endpoints on R is the same
as that of the components' endpoints on P . By considering the endpoints of
the transformed k chords on R as the vertices of a regular 2 k -polygon, one can
easily see that for any two boundary points s and t , there always exists a link-2
component that does not contain s nor t .Thus, P is not link-2 LR -visible. (For
details, see the proof of Lemma 2 of [ 14 ].)