New model-based approaches to digital halftoning are proposed. They are intended primarily for laser printers, which generate 'distortions' such as 'dot overlap'. Conventional methods, such as clustered-dot ordered dither, resist distortions at the expense of spatial and gray-scale resolution. Our methods rely on printer models that predict distortions and, rather than merely resisting them, they exploit them to increase, rather than decrease, gray-scale and spatial resolution. We propose a general framework for printer models, and find a specific model of laser printers. As an example of model-based halftoning we propose a modification of error diffusion, which is often considered the best halftoning method of CRT displays with no significant distortions. The new version exploits the printer model to extend the benefits of error diffusion to printers. Experiments show that it provides high quality reproductions with reasonable complexity. The quality of printed images obtained using the new technique on a 300 dots/inch printer is comparable to the quality of images obtained with traditional techniques (e.g. 'Classical' screening) on a 400 dots/inch printer. Model-based halftoning can be especially useful in transmission of high quality documents using high fidelity gray-scale image encoders. As we show in a companion paper, is such cases halftoning is performed at the receiver, just before printing. Apart form coding efficiency, this approach permits the halftoner to be tuned to the individual printer, whose characteristics may vary considerably from those of other printers, for example, write-black vs. write-white laser printers.