For two points $p$ and $q$ in the plane, a straight
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 a highway that minimizes
the maximum travel time over all pairs of points in
$S$. If the orientation of the highway is fixed,
the optimal highway can be computed in linear time,
both for the $L_1$- and the Euclidean metric as the
underlying metric. If arbitrary orientations are
allowed, then the optimal highway can be computed in
$O(n^2 n)$ time. We also consider the problem
of computing an optimal pair of highways, one being
horizontal, one vertical.
%0 Journal Article
%1 aaabbcknsw-coh-09
%A Ahn, Hee-Kap
%A Alt, Helmut
%A Asano, Tetsuo
%A Bae, Sang Won
%A Brass, Peter
%A Cheong, Otfried
%A Knauer, Christian
%A Na, Hyeon-Suk
%A Shin, Chan-Su
%A Wolff, Alexander
%D 2009
%J International Journal of Foundations of Computer Science
%K city_metric geometric_facility_location min-max-min_problem myown optimal_highways time_metric
%N 1
%P 3--23
%R 10.1142/S0129054109006425
%T Constructing Optimal Highways
%V 20
%X For two points $p$ and $q$ in the plane, a straight
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 a highway that minimizes
the maximum travel time over all pairs of points in
$S$. If the orientation of the highway is fixed,
the optimal highway can be computed in linear time,
both for the $L_1$- and the Euclidean metric as the
underlying metric. If arbitrary orientations are
allowed, then the optimal highway can be computed in
$O(n^2 n)$ time. We also consider the problem
of computing an optimal pair of highways, one being
horizontal, one vertical.
@article{aaabbcknsw-coh-09,
abstract = {For two points $p$ and $q$ in the plane, a straight
line~$h$, called a highway, and a real $v>1$, we
define the \emph{travel time} (also known as the
\emph{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. \par Given a set $S$ of $n$ points in the
plane and a highway speed $v$, we consider the
problem of finding a \emph{highway} that minimizes
the maximum travel time over all pairs of points in
$S$. If the orientation of the highway is fixed,
the optimal highway can be computed in linear time,
both for the $L_1$- and the Euclidean metric as the
underlying metric. If arbitrary orientations are
allowed, then the optimal highway can be computed in
$O(n^{2} \log n)$ time. We also consider the problem
of computing an optimal pair of highways, one being
horizontal, one vertical.},
added-at = {2024-07-14T10:03:47.000+0200},
author = {Ahn, Hee-Kap and Alt, Helmut and Asano, Tetsuo and Bae, Sang Won and Brass, Peter and Cheong, Otfried and Knauer, Christian and Na, Hyeon-Suk and Shin, Chan-Su and Wolff, Alexander},
biburl = {https://www.bibsonomy.org/bibtex/2783f670ea81486452842c079f46ed6f6/awolff},
cites = {ahiklmps-pptml1in-01, ahiklmps-vdsnh-03,
aap-qpsscvd-04, bc-spvdtngp-05, bc-vdtnep-06,
bkc-occvd-06, b-lbact-83, bmm-fasdc-03,
cchlp-mwee-07, cl-mgflp-06, c-garot-99, cm-ecgmp-69,
egs-ueplf-89, fj-gsrsm-84, gsw-ccvdf-07,
sa-dssga-95, t-sgprc-83, ZZZ},
doi = {10.1142/S0129054109006425},
interhash = {806d086ba8f0d11212ee5b42f9e089f0},
intrahash = {783f670ea81486452842c079f46ed6f6},
journal = {International Journal of Foundations of Computer Science},
keywords = {city_metric geometric_facility_location min-max-min_problem myown optimal_highways time_metric},
number = 1,
pages = {3--23},
pdf = {http://www1.pub.informatik.uni-wuerzburg.de/pub/wolff/pub/aaabbcknsw-coh-09.pdf},
succeeds = {aaabbcknsw-coh-07},
timestamp = {2024-07-14T10:03:47.000+0200},
title = {Constructing Optimal Highways},
volume = 20,
year = 2009
}