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