The local and global convergence properties of the Lloyd algorithm [see S. Lloyd, IEEE Trans. Inf. Theory 28, 129–137 (1982; Zbl 0504.94015)] which is a popular iterative scheme for computing the centroidal Voronoi tessellations (CVTs), are studied. The new analytical results proved here [cf. Q. Du, V. Faber and M. Gunzburger, SIAM Rev. 41, 637–676 (1999; Zbl 0983.65021)] are derived through a careful utilization of the optimization properties shared by CVTs. An extension of CVTs to constrained CVTs is also presented. The study of global convergence of the Lloyd algorithm in any dimension for any smooth density is indicated as an important open problem