Constructing optimal highways

H.K. Ahn, H. Alt, T. Asano, S.W. Bae, P. Brass, O. Cheong, C. Knauer, H.S. Na, C.S. Shin, A. Wolff

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)


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.
Original languageEnglish
Title of host publicationProceedings of the 13th Computing: the Australasian Theory Symposium (CATS 2007) 30 January - 2 February 2007, Ballarat, Victoria, Australia
EditorsJ. Gudmundsson, B. Jay
Place of PublicationSydney
PublisherAustralian Computer Society
ISBN (Print)1-920-68246-5
Publication statusPublished - 2007
Eventconference; CATS 2007, Ballarat, Victoria, Australia; 2007-01-30; 2007-02-02 -
Duration: 30 Jan 20072 Feb 2007

Publication series

NameConferences in Research and Practice in Information Technology
ISSN (Print)1445-1336


Conferenceconference; CATS 2007, Ballarat, Victoria, Australia; 2007-01-30; 2007-02-02
OtherCATS 2007, Ballarat, Victoria, Australia


Dive into the research topics of 'Constructing optimal highways'. Together they form a unique fingerprint.

Cite this