Constructing Optimal Highways
<|reference_start|>Constructing Optimal Highways: 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.   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.<|reference_end|>
@article{ahn2007constructing,
    title={Constructing Optimal Highways},
    author={Hee-Kap Ahn and Helmut Alt and Tetsuo Asano and Sang Won Bae and Peter
  Brass and Otfried Cheong and Christian Knauer and Hyeon-Suk Na and Chan-Su
  Shin and Alexander Wolff},
    journal={International Journal of Foundations of Computer Science
  20(2009):3-23},
    year={2007},
    doi={10.1142/S0129054109006425},
    archivePrefix={arXiv},
    eprint={cs/0703037},
    primaryClass={cs.CG}
}