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 -