  Algorithms are given for determining $L_\infty$ isotonic regression of
weighted data. For a linear order, grid in multidimensional space, or tree, of
$n$ vertices, optimal algorithms are given, taking $\Theta(n)$ time. These
improve upon previous algorithms by a factor of $\Omega(\log n)$. For vertices
at arbitrary positions in $d$-dimensional space a $\Theta(n \log^{d-1} n)$
algorithm employs iterative sorting to yield the functionality of a
multidimensional structure while using only $\Theta(n)$ space. The algorithms
utilize a new non-constructive feasibility test on a rendezvous graph, with
bounded error envelopes at each vertex.
