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_html":"<p>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.</p>","abstract_has_math":false,"creators":["Xiao, Xiao"],"institution":null,"degree_name":"M.S.","degree_level":"Campus Access Thesis","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":["Lili Ju"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2010,"date_issued":"2010-01-01T08:00:00Z","date_published":"2010-01-01T08:00:00Z","updated_at":"2026-07-24T04:36:50Z","subjects":["Mathematics","Physical Sciences and Mathematics"],"languages":[],"rights":["© 2010, Xiao Xiao"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://scholarcommons.sc.edu/etd/295","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Lili Ju"]},{"key":"dc:creator","label":"Author","values":["Xiao, Xiao"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Campus Access Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Mathematics","Physical Sciences and Mathematics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["© 2010, Xiao Xiao"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://scholarcommons.sc.edu/etd/295"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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.
"]},{"key":"dc:title","label":"Title","values":["Over-Relaxation Lloyd Method For Computing Centroidal Voronoi Tessellations"]}]}],"canonical_facts":{"dc:contributor":["Lili Ju"],"dc:creator":["Xiao, Xiao"],"dc:description.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.
"],"dc:identifier":["https://scholarcommons.sc.edu/etd/295"],"dc:rights":["© 2010, Xiao Xiao"],"dc:subject":["Mathematics","Physical Sciences and Mathematics"],"dc:title":["Over-Relaxation Lloyd Method For Computing Centroidal Voronoi Tessellations"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Campus Access Thesis"],"thesis:degree_name":["M.S."]},"updated_at":"2026-07-24T04:36:50Z"}