Centroidal power diagrams, Lloyd's algorithm and applications to optimal location problems

Bourne, D.P.; Roper, S.M.

doi:10.1137/141000993

Centroidal power diagrams, Lloyd's algorithm and applications to optimal location problems

Bourne, D.P.; Roper, S.M.

Authors

D.P. Bourne

S.M. Roper

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).

Citation

Bourne, D., & Roper, S. (2015). Centroidal power diagrams, Lloyd's algorithm and applications to optimal location problems. SIAM Journal on Numerical Analysis, 53(6), 2545-2569. https://doi.org/10.1137/141000993

Journal Article Type	Article
Acceptance Date	Aug 24, 2015
Online Publication Date	Nov 5, 2015
Publication Date	Nov 5, 2015
Deposit Date	Dec 22, 2015
Publicly Available Date	Jan 19, 2016
Journal	SIAM Journal on Numerical Analysis
Print ISSN	0036-1429
Electronic ISSN	1095-7170
Publisher	Society for Industrial and Applied Mathematics
Peer Reviewed	Peer Reviewed
Volume	53
Issue	6
Pages	2545-2569
DOI	https://doi.org/10.1137/141000993
Keywords	Voronoi diagram, Power diagram, Lloyd's method, Optimal location problems, Quantization.