In this paper, a high-capacity data hiding is proposed for embedding a large amount of information into halftone images. The embedded watermark can be distributed into several error-diffused images with the proposed minimal-error bit-searching technique (MEBS). The method can also be generalized to self-decoding mode with dot diffusion or color halftone images. From the experiments, the embedded capacity from 33% up to 50% and good quality results are achieved. Furthermore, the proposed MEBS method is also extended for robust watermarking against the degradation from printing-and-scanning and several kinds of distortions. Finally, a least-mean square-based halftoning is developed to produce an edge-enhanced halftone image, and the technique also cooperates with MEBS for all the applications described above, including high-capacity data hiding with secret sharing or self-decoding mode, as well as robust watermarking. The results prove much sharper than the error diffusion or dot diffusion methods.