This paper addresses the problem of converting a 2d digital object S (a finite set of points in \(\mathbb {Z}^2\) ) into a finite set \(\mathcal {B}\) of balls centered on \(\mathbb R^2\) , such that the balls of \(\mathcal {B}\) cover all points of S and no point of \(\mathbb {Z}^2\backslash S\) , and the cardinality of \(\mathcal {B}\) is minimum. In a previous work, we showed that the problem was polynomial for the specific class of 2d hole-free digital objects. In this article, we show that the problem is NP-complete in the general case using a reduction from the 3-Planar Vertex Cover problem.