TY - GEN

T1 - Constructing optimal highways

AU - Ahn, H.K.

AU - Alt, H.

AU - Asano, T.

AU - Bae, S.W.

AU - Brass, P.

AU - Cheong, O.

AU - Knauer, C.

AU - Na, H.S.

AU - Shin, C.S.

AU - Wolff, A.

PY - 2007

Y1 - 2007

N2 - 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.

AB - 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.

M3 - Conference contribution

SN - 1-920-68246-5

T3 - Conferences in Research and Practice in Information Technology

SP - 7

EP - 14

BT - Proceedings of the 13th Computing: the Australasian Theory Symposium (CATS 2007) 30 January - 2 February 2007, Ballarat, Victoria, Australia

A2 - Gudmundsson, J.

A2 - Jay, B.

PB - Australian Computer Society

CY - Sydney

T2 - conference; CATS 2007, Ballarat, Victoria, Australia; 2007-01-30; 2007-02-02

Y2 - 30 January 2007 through 2 February 2007

ER -