Confidence bands for isotonic median curves using sign tests

Suppose that one observes independent random variables (X-1, Y-1), (X-2, Y-2),..., (X-n, Y-n) in R-2 with unknown distributions, except that Median(Y-i\X-i = x) = M(x) for some unknown isotonic function M. We describe an explicit algorithm for the computation of confidence bands for the median function M whose running time is of order O(n(2)). The bands rely on multiscale sign tests and are shown to have desirable asymptotic properties.