Abstract
In this paper we develop a numerical method for solving a class of optimization problems known as optimal location or quantization problems. The target energy can be written either in terms of atomic measures and the Wasserstein distance or in terms of weighted points and power diagrams (generalized Voronoi diagrams). The latter formulation is more suitable for computation. We show that critical points of the energy are centroidal power diagrams, which are generalizations of centroidal Voronoi tessellations, and that they can be approximated by a generalization of Lloyd's algorithm (Lloyd's algorithm is a common method for finding centroidal Voronoi tessellations). We prove that the algorithm is energy decreasing and prove a convergence theorem. Numerical experiments suggest that the algorithm converges linearly. We illustrate the algorithm in two and three dimensions using simple models of optimal location and crystallization (see online supplementary material).
Original language  English 

Pages (fromto)  25452569 
Number of pages  25 
Journal  SIAM Journal on Numerical Analysis 
Volume  53 
Issue number  6 
DOIs  
Publication status  Published  5 Nov 2015 
Keywords
 Lloyd's method
 Optimal location problems
 Power diagram
 Quantization
 Voronoi diagram
ASJC Scopus subject areas
 Numerical Analysis
Fingerprint Dive into the research topics of 'Centroidal power diagrams, Lloyd's algorithm, and applications to optimal location problems'. Together they form a unique fingerprint.
Profiles

David Bourne
 School of Mathematical & Computer Sciences  Associate Professor
 School of Mathematical & Computer Sciences, Mathematics  Associate Professor
Person: Academic (Research & Teaching)