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

FF2(b)

BB1(a)

a

BB1(b)

BB2(a)

BB2(a)

a

c

b

FF1(c) FF1(b)

BB1(b)

b

p

BB2(b)

FF2(c)

(a)

(b)

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

Remark. The conditions N1 , N2 and N3 given in [ 9 ] for characterizing the
k -searchable polygons make use of the concept of essential cuts , which are essen-
tially the same as the non-redundant components. The condition N1 consists
of A1 and one more situation of three disjoint link-2 components (Lemma 2 ),
and N2 describes the same situation as stated in Lemma 3 . The condition N3
is essentially the same as A3 . Thus, the forbidden situations described by the
conditions N1 , N2 and N3 in [ 9 ] are the same as those by A1 , A2 and A3 .
Note also that the polygons shown in Fig. 6 are link-2 LR -visible.
First, we can check in O ( n log n ) time whether P is link-2 LR -visible (The-
orem 3 ). If not , then P is not 2-searchable. Assume now that P is link-2 LR -
visible. It is easy to see that all the components satisfying A3 are essentially
non-redundant. Also, if there are three components satisfying A1 , then they are
non-redundant; otherwise, there are three pairwise disjoint link-2 components,
contradicting the assumption that P is link-2 LR -visible.
Suppose that all non-redundant backward (forward) link-2 components (they
may be the ʱ -or ʲ -components) have been computed, and their endpoints are
ordered by a clockwise wise of P , starting at an arbitrary boundary point. For a
boundary point p , we can in O (1) time find a non-redundant backward (forward)
link-2 component C ( C ), whose left (right) endpoint is closest to p clockwise
(counterclockwise), starting at p . By scanning on the boundary of P once, we can
then determine in O ( n ) time whether the condition A3 is satisfied. Analogously,
for a non-redundant component C (e.g., the link-2 component of a in Fig. 6 (a)),
we can also in O (1) time find a non-redundant forward (backward) link-2 com-
ponent D ( D ), which is closest to the left (right) endpoint of C in clockwise
(counterclockwise) direction. Such a triple of the components, if it exists, can
also be found in O ( n ) time. Hence, whether the condition A1 is satisfied in P
can be verified in O ( n ) time. Putting together all the above results, we obtain
the following result.

Theorem 4. For a given polygon P , one can determine in O ( n log n ) time
whether P is searchable by a k -searcher, where k (

≥

2) is a fixed, positive integer.