  This work investigates functional source coding problems with maximal
distortion, motivated by approximate function computation in many modern
applications. The maximal distortion treats imprecise reconstruction of a
function value as good as perfect computation if it deviates less than a
tolerance level, while treating reconstruction that differs by more than that
level as a failure. Using a geometric understanding of the maximal distortion,
we propose a hypergraph-based source coding scheme for function computation
that is constructive in the sense that it gives an explicit procedure for
finding optimal or good auxiliary random variables. Moreover, we find that the
hypergraph-based coding scheme achieves the optimal rate-distortion function in
the setting of coding for computing with side information and achieves the
Berger-Tung sum-rate inner bound in the setting of distributed source coding
for computing. It also achieves the El Gamal-Cover inner bound for multiple
description coding for computing and is optimal for successive refinement and
cascade multiple description problems for computing. Lastly, the benefit of
complexity reduction of finding a forward test channel is shown for a class of
Markov sources.
