Paper Info
Title
Point location in the continuous-time moving network
Abstract
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 logm)) time with O(nmW log2m + n2logn + nE) time and O(nmW logm + 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 logm)) 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 logm)) time.
Year
DOI
Venue
2010
10.1007/978-3-642-14355-7_14
AAIM
Keywords
Field
DocType
query point p,preprocessing time,m site,network graph,network edge,mw logm,network voronoi diagram,time information,e edge,point location,nmw logm,voronoi diagram
Graph,Combinatorics,Point location,Vertex (geometry),Computer science,Spacetime,Edge device,Voronoi diagram
Conference
Volume
ISSN
ISBN
6124
0302-9743
3-642-14354-7
Citations 
PageRank 
References 
0
0.34
8
Authors
2
Name
Order
Citations
PageRank
Chenglin Fan1287.24
Jun Luo222226.61