%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 #IJFCS# %K timemetric citymetric Geometricfacilitylocation optimalhighways min-max-minproblem %N 1 %P 3--23 %R 10.1142/S0129054109006425 %T Constructing Optimal Highways %U http://dx.doi.org/10.1142/S0129054109006425 %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 = {2010-04-13T09:41:23.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/242c23c4dd1d45e63852161d6e5e2425b/fink}, 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 = {42c23c4dd1d45e63852161d6e5e2425b}, journal = {#IJFCS#}, keywords = {timemetric citymetric Geometricfacilitylocation optimalhighways min-max-minproblem}, number = 1, pages = {3--23}, pdf = {#AWPUBURL#aaabbcknsw-coh-09.pdf}, succeeds = {aaabbcknsw-coh-07}, timestamp = {2010-04-13T09:41:23.000+0200}, title = {Constructing Optimal Highways}, url = {http://dx.doi.org/10.1142/S0129054109006425}, volume = 20, year = 2009 }