Anisotropic mesh generation is important for interpolation and numerical modeling. Recently, Labelle and Shewchuk proposed a two-dimensional guaranteed-quality anisotropic mesh generation algorithm called a Voronoi refinement algorithm. This algorithm treats only domains with straight lines as inputs. In many applications, however, input domains have many curves and the exact representation of curves is required for efficient numerical modeling. In this paper, we extend the Voronoi refinement algorithm and propose it as a guaranteed-quality anisotropic mesh generation algorithm for domains with curved boundaries. Some experimental results are also shown. (C) 2008 Elsevier Ltd. All rights reserved.