Throw a straight line at random into a plane, within which is
inscribed a square grid. Color black each grid vertex that lies above the line,
and white each vertex below it. Now remove the line, and attempt to reconstruct
it from the pattern of vertex colors in an $m \times m$ section of the grid. We
show that for all $\varepsilon > 0$, the line can be approximated to within
order $m^{-1}(\log m)(\log \log m)^{1+\varepsilon}$, with probability 1, and
that there is no deterministic subsequence along which the best achievable rate
is better than $(m \log m)^{-1}(\log \log m)^{-1-\varepsilon}$ with positive
probability. Both these results fail if $\varepsilon = 0$. More generally, we
provide a complete characterization of almost sure rates of approximation, in
terms of the convergence or divergence of an infinite series. Applying these
results, we develop near-optimal local linear approximations to general smooth
boundaries. We address the case where vertex color is a shade of gray, varying
in the continuum and subject to stochastic error.