  We consider the problem of recovering characteristic functions
$u:=\chi_\Omega$ from cell-average data on a coarse grid, and where $\Omega$ is
a compact set of $\mathbb{R}^d$. This task arises in very different contexts
such as image processing, inverse problems, and the accurate treatment of
interfaces in finite volume schemes. While linear recovery methods are known to
perform poorly, nonlinear strategies based on local reconstructions of the jump
interface $\Gamma:=\partial\Omega$ by geometrically simpler interfaces may
offer significant improvements. We study two main families of local
reconstruction schemes, the first one based on nonlinear least-squares fitting,
the second one based on the explicit computation of a polynomial-shaped curve
fitting the data, which yields simpler numerical computations and high order
geometric fitting. For each of them, we derive a general theoretical framework
which allows us to control the recovery error by the error of best
approximation up to a fixed multiplicative constant. Numerical tests in 2d
illustrate the expected approximation order of these strategies. Several
extensions are discussed, in particular the treatment of piecewise smooth
interfaces with corners.
