For two points p and q in the plane, a (unbounded) line h, called a highway, and a real v > 1, we define the travel time (also known as the city distance) from p and q to be the time needed to traverse a quickest path from p to q, where the distance is measured with speed v on h and with speed 1 in the underlying metric elsewhere. Given a set S of n points in the plane and a highway speed v, we consider the problem of finding an axis-parallel line, the highway, that minimizes the maximum travel time over all pairs of points in S. We achieve a linear-time algorithm both for the L1- and the Euclidean metric as the underlying metric. We also consider the problem of computing an optimal pair of highways, one being horizontal, one vertical.
Cite as: Ahn, H.-K., Alt, H., Asano, T., Bae, S.W., Brass, P., Cheong, O., Knauer, C., Na, H.-S., Shin, C.-S. and Wolff, A. (2007). Constructing Optimal Highways. In Proc. Thirteenth Computing: The Australasian Theory Symposium (CATS2007), Ballarat, Australia. CRPIT, 65. Gudmundsson, J. and Jay, B., Eds. ACS. 7-14.
(from crpit.com)
(local if available)