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 high-way 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.
|Name||Conferences in Research and Practice in Information Technology|
|Conference||conference; CATS 2007, Ballarat, Victoria, Australia; 2007-01-30; 2007-02-02|
|Period||30/01/07 → 2/02/07|
|Other||CATS 2007, Ballarat, Victoria, Australia|