Title : Constructing Optimal Axis-Parallel Highways

  For two points $p$ and $q$ in the plane, a line $h$---the
  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 distances
  are measured in the underlying metric, and the speed on $h$ is $v$ 
  and elsewhere 1.  Given a set $S$ of $n$ points
  in the plane and a highway speed $v$, we consider the problem of finding
  an axis-parallel line that minimizes the maximum travel time over all
  pairs of points in $S$. In the case of the $L_1$-metric, we achieve a linear
  time algorithm. In the case of the Euclidean metric, 
  our algorithms run in time $O(n \log n)$.
  We also show that placing $k$ parallel highways does not reduce the
  maximum travel time.

Participants : Hee-Kap, Helmut, Tetsuo, Sang Won, Otfried, Chan-Su, Alex.