Information Technology Reference
In-Depth Information
B(p)
p'
p
BB1(p)
B(p')
B(r)
r
BB1(r)
BB2(r)
BB2(p)
Fig. 4.
Computing the link-2 ray-shootings.
BB
2(
r
)] using the linear-time algorithm [
5
]. The last turing point of a path,
say,
SP
(
B
(
r
)
,B
(
p
)), can then be reported in
O
(log
n
) time (Lemma
4
), and a
link-2 backward ray-shooting can also be computed in
O
(log
n
) time (Lemma
5
).
Hence, all the backward link-2
ʱ
r
-components can be calculated in
O
(
n
log
n
)
time.
Lemma 6.
For a non-redundant backward link-2 component of
r
,wecancom-
pute in
O
(
n
log
n
)
time all the backward link-2
ʱ
r
-components, whose defining
vertices belong to the backward link-2
ʱ
-component of
r
.
Calling the Procedure of Computing the Link-2
α
r
-Components Three
Times.
It follows from Lemma
2
that the procedure given in the previous section
needs to be performed for at most three non-redundant backward link-2
ʱ
-
components; either a superset of the backward link-2
ʱ
-components is eventually
computed, or three (pairwise) disjoint components are found. In the latter case,
P
is not link-2
LR
-visible.
Let us now describe how to find three non-redundant backward link-2
ʱ
-
components, to which the above procedure applies. Assume first that the back-
ward component of a reflex vertex
r
is non-redundant. The backward link-2
comp
onent
of
r
can then be found fr
om th
e visibility polygon of the line seg-
ment
rB
(
r
). The visibility polygon of
rB
(
r
)in
P
can be computed in linear time
[
5
]. Assume also that the backward link-2
ʱ
-component
P
[
BB
1(
r
)
,BB
2(
r
)] is
found. See Fig.
5
. Next, find the first reflex vertex
v
, by a counterclockwise
scan from
BB
2(
r
)to
BB
1(
r
), such that
P
[
BB
1(
v
)
,BB
2(
v
)] is contained in
P
[
BB
1(
r
)
,BB
2(
r
)] (Fig.
5
). From Lemmas
4
and
5
, it can simply be done in
O
(
n
log
n
) time. If no vertex
v
exists, the backward link-2
ʱ
-component of
r
is non-redundant, with respect to all backward link-2
ʱ
-components (Fig.
5
(c)).
Otherwise, since
v
is the first vertex, in the counterclockwise scan from
BB
2(
r
)
to
BB
1(
r
), such that
P
[
BB
1(
v
)
,BB
2(
v
)] is contained in
P
[
BB
1(
r
)
,BB
2(
r
)],
the backward link-2
ʱ
-component of
v
is non-redundant. See Figs.
5
(a)-(b). (The
backward link-2
ʱ
-component of
r
may be redundant, see Fig.
5
(a).)
Search WWH ::
Custom Search