Over-Relaxation Lloyd Method For Computing Centroidal Voronoi Tessellations
type: CreativeWork
description: 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.
abstract: 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.
author: Xiao, Xiao
keywords: Mathematics, Physical Sciences and Mathematics
date published: 2010-01-01T08:00:00Z
date modified: 2026-07-24T04:36:50Z
provider: University of South Carolina
publisher: Networked Digital Library of Theses and Dissertations
type: WebPage
source organization: University of South Carolina