loading...
Time Convex Hull with a Highway
University of Glamorgan, Pontypridd, Wales July 09-July 11
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ISVD.2007.384th International Symposium on Vorono ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Teng-Kai Yu, National Taiwan University, Taiwan
D. T. Lee, National Taiwan University, Taiwan
We consider the problem of computing the time convex hull of a set of points in the presence of a straight-line highway in the plane. The traveling speed in the plane is assumed to be much slower than that along the highway. The shortest time path between two arbitrary points is either the straight-line segment connecting these two points or a path that passes through the highway. The time convex hull, CH_t(P), of a set P of n points is the smallest set containing P such that all the shortest time paths between any two points lie in CH_t(P). In this paper we give a \Theta(n log n) time algorithm for solving the time convex hull problem for a set of n points in the presence of a highway.
Citation:
Teng-Kai Yu, D. T. Lee, "Time Convex Hull with a Highway," isvd, pp.240-250, 4th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2007), 2007
Usage of this product signifies your acceptance of the Terms of Use.