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

C

C

B B1(a)

a

b d BB2(a)

BB2(a)

c

b

a

FB2(c c

e

BB1(b)

BB2(e)

FF1(c)

BB2(d)

FF2(c) BB2(b) FF2(b)

(a)

(b)

Fig. 3. Two types of the polygons which are not link-2 LR -visible.

Theorem 2. A polygon P is link-2 LR -visible if and only if there do not exist
k non-redundant link-2 components (they may be the ʱ -or ʲ -components) such
that each of them exactly intersects with k other components, where 0 k ≤ ≤

k − 3 .

Proof. The necessity directly follows from Lemmas 2 and 3 . Assume now that
there do not exist k non-redundant link-2 components in P such that each of
them exactly intersects with k other components, where 0 k ≤

3. As in the
proof of Theorem 1 of [ 14 ], we can classify all non-redundant link-2 components
(including both ʱ -components and ʲ -components) into two groups such that
the common intersection of the components in either group is not empty. Thus,
we can find two boundary points s and t , one per group, such that P is link-2
LR -visible with respect to s and t (Lemma 1 ).

≤ k −

4 Recognizing Link-2 LR -visibility Polygons

In this section, we present an O ( n log n ) time algorithm for determining whether
a given polygon P is link-2 LR -visible as well as for reporting a pair or all
pairs ( s, t ) which admit link-2 LR -visibility. A main procedure is to compute
a superset of all non-redundant backward link-2 ʱ -components. A symmetric
procedure does the same for the forward link-2 ʱ -components. As described in
[ 3 ], the non-redundant link-2 ʱ -components can then be extracted from these two
sets. Analogously, we compute the non-redundant link-2 ʲ -components. After all
non-redundant link-2 components are computed, we can determine whether P
is link-2 LR -visible (Theorem 2 ).
By symmetry, we give below only the procedure for computing a superset of
non-redundant link-2 backward ʱ -components. We will make use of the shortest
path trees, rooted at some polygon vertices. The shortest path between two points
a and b of P , denoted by SP ( a, b ), is the Euclidean minimum-distance curve with
the endpoints a and b inside P . The path SP ( a, b ) is always a polygonal chain,