Advertisement
Published in:
2010 | OriginalPaper | Chapter
Point Location in the Continuous-Time Moving Network
Authors : Chenglin Fan, Jun Luo
Published in: Algorithmic Aspects in Information and Management
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We discuss two variations of the moving network Voronoi diagram. The first one addresses the following problem: given a network with
n
vertices and
E
edges. Suppose there are
m
sites (cars, postmen,
etc
) moving along the network edges and we know their moving trajectories with time information. Which site is the nearest one to a point
p
located on network edge at time
t
′? We present an algorithm to answer this query in
O
(log(
mW
log
m
)) time with
O
(
nmW
log
2
m
+
n
2
log
n
+
nE
) time and
O
(
nmW
log
m
+
E
) space for preprocessing step, where
E
is the number of edges of the network graph (the definition of
W
is in section 3). The second variation views query point
p
as a customer with walking speed
v
. The question is which site he can catch the first? We can answer this query in
O
(
m
+ log(
mW
log
m
)) time with same preprocessing time and space as the first case. If the customer is located at some node, then the query can be answered in
O
(log(
mW
log
m
)) time.