A halftone dot addition device for adding halftone dots to halftone dot images includes an empty circle information acquiring unit and a halftone dot addition unit. The empty circle information acquiring unit obtains, in a Voronoi diagram having a generatrix corresponding to a halftone dot in a halftone dot image. The radius of an empty circle is a circle centering on a Voronoi vertex. The empty circle passes through the generatrix but not internally includes the generatrix. The halftone dot addition unit, if the radius of a target circle being the empty circle obtained, as a target, by the empty circle information acquiring unit is larger than a specific value, adds to the halftone dot image a halftone dot corresponding to a new generatrix, by adding the new generatrix to the inside of the target circle.