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

characterizing and recognizing LR -visibility polygons has received much atten-
tion in computational geometry and robotics [ 1 , 3 , 4 , 10 ]. Tseng et al. [ 15 ] were
thefirsttoproposean O ( n log n ) time algorithm for deciding whether a given
polygon is LR -visible. The time bound was later improved to O ( n ) by Das et al.
[ 3 ]. (One can also report all pairs ( s, t ) which admit LR -visibility, after deter-
mining the LR -visibility of a polygon [ 3 , 15 ].) Very recently, Tan et al. showed
that a polygon P is not LR -visible if and only if it contains k non-redundant
components such that each of them exactly intersects with k other components,
0 k

3, and presented an alternative, simpler algorithm for character-
izing LR -visibility polygons [ 14 ]. The backward and forward components of a
reflex vertex r are the clockwise and counterclockwise boundary chains from r
to its backward and forward ray-shootings, respectively. A component is non-
redundant if it does not contain any other component.
In this paper, we study the link-2 LR -visibility polygons, which are a gener-
alization of LR -visibility polygons. Two points x, y

≤ ≤ k −

∈ P are said to be mutually

link-2 visible if there exists the third point z P such that z is visible from

both x and y . A polygon P is link-2 LR -visible if there are two points s , t on
the boundary of P such that every point on the clockwise boundary of P from
s to t is link-2 visible from some point of the other boundary of P from t to s
and vice versa.
In the rest of this paper, we first give a characterization of link-2 LR -visibility
polygons. It is obtained by introducing the new concepts of link-2 ray-shootings
and components, and establishing the forbidden patterns for link-2 LR -visibility
polygons, which are a direct generalization of the same structures for LR -
visibility polygons. Next, we develop an O ( n log n ) time algorithm to determine
whether a given polygon is link-2 LR -visible. Using the characterization of link-
2 LR -visibility polygons, we further present an O ( n log n ) time algorithm for
determining whether a polygonal region is searchable by a k -searcher, k

∈

≥ 2.

This improves upon the previous O ( n 2 ) time bound [ 9 ].

2 Preliminaries

Let P denote a simple polygon with n vertices, i.e., P has neither self-intersections
nor holes. Two points x , y P are said to be mutually visible if the line segment

connecting them, denoted by xy , is entirely contained in P . For two regions Q 1 ,
Q 2

∈

P , we say that Q 1 is weakly visible from Q 2 if every point in Q 1 is visible
from some point in Q 2 .
For a vertex x of the polygon P ,let Succ ( x ) denote the vertex immediately
succeeding x clockwise, and Pred ( x ) the vertex immediately preceding x clock-
wise. A vertex of P is reflex if its interior angle is strictly greater than 180 ◦ ;
otherwise, it is convex . An important definition for reflex vertices is that of ray-
shootings : the backward ray-shooting from a reflex vertex r , denoted by B(r) ,is
the first point of P hit by a “bullet” shot at r in the direction from Succ ( r )to
r , and the forward ray-shooting F(r) is the first point hit by the bullet shot at
r in the direction from Pred ( r )to r .

ↆ