Time Convex Hull with two Highways
Date Issued
2008
Date
2008
Author(s)
Wang, Hung-Kai
Abstract
We consider the problem of computing the time convex hull of a set of n points in the presence of two straight-line highways in the plane. The traveling speed in the plane is assumed to be much slower than that along the highways. 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(s). The time convex hull, CHt(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 CHt(P). In this thesis we give a θ(n log n) time algorithm for solving the time convex hull problem for a set of n points in the presence of two highways.
Subjects
time convex hull
convex hull
highway
cluster.
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-97-R95922130-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):3d30fcddb8911a2a7ef4161f9ebbff0c