Information Technology Reference
In-Depth Information
whose turning points are the vertices of
P
.The
shortest path tree
from a vertex
v
of
P
is the union of all shortest paths
SP
(
v, w
), for each vertex
w
(
=
v
)of
P
.
The following two results have been known in the literature.
Lemma 4
(See [
6
,
7
])
.
The polygon
P
can be preprocessed in
O
(
n
)
time so that
a shortest path query between two given points can be answered in logarithmic
time plus the time required to report the path itself.
Lemma 5
(See [
2
])
.
The polygon
P
can be preproceessed in
O
(
n
log
n
)
time so
that a ray-shooting query can be answered in
O
(log
n
)
time.
4.1 Computing All Non-redundant Backward Link-2
α
-Components
We consider below only backward link-2
ʱ
-components. Also, we say a backward
link-2
ʱ
-component is
non-redundant
, if it does not contain any other link-2
backward
ʱ
-component.
We will first present a method to compute all the backward link-2
ʱ
-
components, whose defining vertices belong to a non-redundant backward link-2
ʱ
-component. The restriction of the defining vertices to a non-redundant link-
2
ʱ
-component makes it easy to find all the backward link-2
ʱ
-components in
O
(
n
log
n
) time. From Lemma
2
, this procedure needs to be performed at most
three times.
α
All Defining Vertices are Limited to a Non-redundant link-2
-
Component.
Suppose that the backward link-2
ʱ
-component
P
[
BB
1(
r
)
,
BB
2(
r
)] of some vertex
r
is non-redundant. We describe below a procedure
to compute all the backward link-2
ʱ
-components, which intersect
P
[
BB
1(
r
)
,
BB
2(
r
)] and whose defining vertices are contained in
P
[
BB
1(
r
)
,BB
2(
r
)].
(Remember that it suces to compute a
superset
of all non-redundant backward
link-2
ʱ
-components.) For simplicity, we term these components the backward
link-2
ʱ
r
-components.
Assume that the backward component of a vertex
p
P
[
BB
1(
r
)
,BB
2(
r
)]
is non-redundant. If
B
(
p
) is visible from
B
(
r
), then the backward link-2 ray-
shooting of
p
(e.g., the vertex
p
in Fig.
4
), if it exists, contains that of
r
and is
thus redundant. Otherwise, the last turning point of the path
SP
(
B
1(
r
)
,B
(
p
))
is the vertex
BB
1(
p
), and the link-2 ray-shooting
BB
2(
p
) is the boundary point
hit by the “bullet” shot at
BB
1(
p
) in the direction from
B
(
p
)to
BB
1(
p
). In this
case,
BB
2(
p
)
∈
ↂ
P
[
BB
1(
r
)
,BB
2(
r
)], contradicting the assumption that the link-2 component
P
[
BB
1(
r
)
,BB
2(
r
)] is non-redundant. In this way, all the backward link-2
ʱ
r
-
components can be computed.
Consider now the time required to compute the backward link-2
ʱ
r
-
components. First, all non-redundant backward components in
P
can be com-
puted
O
(
n
log
n
) time using the ray-shooting algorithm [
2
,
3
] (or even in
O
(
n
)
time [
13
]). Next, we compute the shortest paths from
B
(
r
) to all the endpoints
of the non-redundant backward components, which are contained in
P
[
BB
1(
r
)
,
∈
P
(
BB
2(
r
)
,BB
1(
r
)) (Fig.
4
); otherwise,
P
[
BB
1(
p
)
,BB
2(
p
)]
Search WWH ::
Custom Search