Information Technology Reference
In-Depth Information
A Characterization of Link-2 LR-visibility
Polygons with Applications
B
Xuehou Tan
1
,
2(
)
, Jing Zhang
1
, and Bo Jiang
1
1
Dalian Maritime University, Linghai Road 1, Dalian, China
2
Tokai University, 4-1-1 Kitakaname, Hiratsuka 259-1292, Japan
tan@wing.ncc.u-tokai.ac.jp
Abstract.
Two points
x, y
inside a polygon
P
are said to be mutu-
ally
link-2
visible if there exists the third point
z ∈ P
such that
z
is
visible from both
x
and
y
. The 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
P
s
t
clockwise boundary of
from
to
is link-2 visible from some point
of the other boundary of
P
from
t
to
s
and vice versa. We give a char-
acterization of link-2
LR
-visibility polygons by generalizing the known
result on
-visibility polygons. A main idea is to extend the concepts of
ray-shootings and components to those under notion of link-2 visibility.
Then, 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 polygo-
nal region is searchable by a
k
-searcher,
k ≥
2, improving upon the pre-
vious
O
(
n
2
) time bound. A polygonal region is 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. Our result can also be used to simplify the existing
solutions of other polygon search problems.
LR
1
Introduction
Let
P
denote a simple polygon with
n
vertices. Any two points
s
and
t
on
P
divide the boundary of
P
into two subchains, which we call
L
and
R
, for left and
right chains. The
LR
-visibility question asks whether each point of
L
is visible
from a point of
R
, and whether each point of
R
is visible from a point of
L
.If
the answer is
yes
,wesay
P
is
LR
-visible with respect to
s
and
t
. If there exists
a pair of points on
P
such that
P
is
LR
-visible with respect to them, we simply
say
P
is
LR
-visible.
Because of its relation to other problems in polygonal visibility (e.g., the
two-guard problem [
15
] and the polygon search problem [
9
,
12
]), the problem of
This work was partially supported by the Grant-in-Aid (MEXT/JSPS KAKENHI
23500024) for Scientific Research from Japan Society for the Promotion of Science
and the National Natural Science Foundation of China under grant 61173034.
Search WWH ::
Custom Search