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

ʲ -components analogously. As shown in Sect. 3 , the non-redundant link-2 ʱ -
components and ʲ -components for link-2 LR -visible polygons have the same
property as the non-redundant components for LR -visible polygons. We can
then determine in O ( n ) time whether P is link-2 LR -visible, and if yes report
a pair ( s, t ) such that P is link-2 LR -visible with respect to s and t , using the
same purpose algorithm of [ 14 ]for LR -visibility polygons. After all link-2 non-
redundant components are computed, the algorithm ALL 2-CUTTABL PAIRS
of [ 15 ] can also be used to report all pairs s and t that admit link-2 LR -visibility.
We summarize our result in the following theorem.

Theorem 3. For a given polygon P ,onecanin O ( n log n ) time determine
whether P is link-2 LR -visible, and if so, report a pair or all pairs ( s, t ) which
admit link-2 LR -visibility.

5 Applications

In this section, we discuss on the application of our characterization of link-2 LR -
visibility polygons to the polygon search problem and other visibility problems
as well.
A polygonal region P is said to be searchable by a searcher if the searcher
can detect (or see) an unpredictable intruder inside the region, no matter how
fast the intruder moves. A k -searcher holds k flashlights and can see only along
the rays of the flashlights emanating from his position. It has been known that
searchability of an -searcher is the same as that of a 2-searcher [ 9 ]. This result

is obtained by characterizing the polygons which are searchable by a k -searcher,
k

∞

2. An O ( n 2 ) time solution to the polygon search problem for a 2-searcher was
then claimed in [ 8 ]. Note that P is not searchable by a 1-searcher (a 2-searcher)
if P is not LR -visible (link-2 LR -visible) [ 12 ].
In the following, we present an O ( n log n ) time algorithm for determining
whether a polygonal region is searchable by a 2-searcher. Our results improves
upon the previous O ( n 2 ) time bound [ 9 ]. To this end, we first recall the char-
acterization of the 2-searchable polygons in terms of the non-redundant link-2
components (which may be the ʱ -or ʲ -components.)

≥

Lemma 8. (See [ 9 ].) A polygon P is searchable by a 2-searcher, if and only if
none of the following conditions holds:

A1 There are three link-2 components in P such that one forward component
intersects the other backward component and the third is disjoint from both
the intersecting components (see Fig. 6 (a)).
A2 The polygon P is not link-2 LR -visible.
A3 For any boundary point p , there are a backward link-2 component C and a
forward link-2 component C such that p is not contained in both C and C
(see Fig. 6 (b)).