Over-Relaxation Lloyd Method For Computing Centroidal Voronoi Tessellations
Centrodial Voronoi tessellation (CVT) is a Voronoi tessellation of a region whose generating points are also the mass centroids of the corresponding Voronoi regions. Centrodial Voronoi tessellations have diverse applications in many areas of science and engineering. In this paper, we study acceleration of the classic iterative algorithm-- Lloyd Method for computing CVTs by applying over-relaxation schemes in the iteration process. Optimal choices of the over-relaxation parameter are studies theoretically. We also verify our results and show faster convergence of the proposed over-relaxtion Lloyd method through various numerical experiments in one and two dimensions.
Mathematics, Physical Sciences and Mathematics
Networked Digital Library of Theses and Dissertations