We propose a novel data hiding method for halftone images with homogeneous distribution of embedding positions . The embedding positions are selected randomly. Then a void-and-cluster algorithm is applied to manipulate the positions to form homogeneous distribution. As a result, pleasing visual quality of the halftone image can be obtained. The proposed method is suitable for high payload data-hiding with fantastic image quality. Furthermore, the proposed method can be extended to watermarking mode. Robustness against tampering, cropping, noise addition, filtering, and print-and-scan attacks can be achieved as well.