Digital halftoning is an important technique to convert a
continuous-tone image into a black-and-white binary image
which looks similar to an input image. A number of algorithms
have been proposed for beatiful and pleasent output pictures.
They have been evaluated mainly by human visual comparisons
based on experiments for several standard images.
I this talk I will talk about algorithmic aspects of the
digital halftoning. You will see surprisingly many different
topics on algorithms and discrete geometry are related to it.
A main topics is to define an optimally halftoned image based
on some mathematical criterion. In this talk the similarity
between two images is measured by the total sum of differences
in the weighted sums of brightness levels of pixels in a
neighborhood surrounding each pixel. Then, the problem of
producing an optimally halftoned image becomes a combinatorial
optimization problem to find a binary image minimizing this
measure for a given multiple-level image. Despite a negative
result that it is NP-complete even for a simple neighborhood
consisting of $2\times 2$ pixels, we can rely on approximation
algorithms mainly based on network flow algorithms.