## Institute for Mathematical Sciences

## Preprint ims04-02

** R. L. Adler, B. Kitchens, M. Martens, C. Pugh, M. Shub and**
* Title: Convex Dynamics and Applications*

Abstract: This paper proves a theorem about bounding orbits of a time dependent dynamical system. The maps that are involved are
examples in convex dynamics, by which we mean the dynamics of
piecewise isometries where the pieces are convex. The theorem came
to the attention of the authors in connection with the problem of
digital halftoning. \textit{Digital halftoning} is a family of
printing technologies for getting full color images from only a
few different colors deposited at dots all of the same size. The
simplest version consist in obtaining grey scale images from only
black and white dots. A corollary of the theorem is that for
\textit{error diffusion}, one of the methods of digital
halftoning, averages of colors of the printed dots converge to
averages of the colors taken from the same dots of the actual
images. Digital printing is a special case of a much wider class
of scheduling problems to which the theorem applies. Convex
dynamics has roots in classical areas of mathematics such as
symbolic dynamics, Diophantine approximation, and the theory of
uniform distributions.

View ims04-02 (PDF format)