Abstract:
|
In this paper we extend the Rectilinear 1-center as follows: Given a set S of n points in the plane, we are interested in locating a facility point f and a rapid transit line (highway) H that together minimize the expression max p ∈ S d H (p,f), where d H (p,f) is the travel time between p and f. A point p ∈ S uses H to reach f if H saves time for p. We solve the problem in O(n 2) or O(nlogn) time, depending on whether or not the highway’s length is fixed. |