Year: 2012
Numerical Mathematics: Theory, Methods and Applications, Vol. 5 (2012), Iss. 2 : pp. 242–259
Abstract
In a variety of modern applications there arises a need to tessellate the domain into representative regions, called Voronoi cells. A particular type of such tessellations, called centroidal Voronoi tessellations or CVTs, are in big demand due to their optimality properties important for many applications. The availability of fast and reliable algorithms for their construction is crucial for their successful use in practical settings. This paper introduces a new multigrid algorithm for constructing CVTs that is based on the MG/Opt algorithm that was originally designed to solve large nonlinear optimization problems. Uniform convergence of the new method and its speedup comparing to existing techniques are demonstrated for linear and nonlinear densities for several 1d and 2d problems, and $O(k)$ complexity estimation is provided for a problem with $k$ generators.
You do not have full access to this article.
Already a Subscriber? Sign in as an individual or via your institution
Journal Article Details
Publisher Name: Global Science Press
Language: English
DOI: https://doi.org/10.4208/nmtma.2012.m1046
Numerical Mathematics: Theory, Methods and Applications, Vol. 5 (2012), Iss. 2 : pp. 242–259
Published online: 2012-01
AMS Subject Headings:
Copyright: COPYRIGHT: © Global Science Press
Pages: 18
Keywords: Centroidal Voronoi tessellation optimal quantization truncated Newton method Lloyd's algorithm multilevel method uniform convergence.
-
Properties of a class of multilevel optimization algorithms for equality-constrained problems
Nash, Stephen G.
Optimization Methods and Software, Vol. 29 (2014), Iss. 1 P.137
https://doi.org/10.1080/10556788.2012.759571 [Citations: 9] -
Centroidal Voronoi tessellation based methods for optimal rain gauge location prediction
Di, Zichao (Wendy) | Maggioni, Viviana | Mei, Yiwen | Vazquez, Marilyn | Houser, Paul | Emelianenko, MariaJournal of Hydrology, Vol. 584 (2020), Iss. P.124651
https://doi.org/10.1016/j.jhydrol.2020.124651 [Citations: 14] -
An Iterative Algorithm for Computing Measures of Generalized Voronoi Regions
Larsson, Lisa J. | Choksi, Rustum | Nave, Jean-ChristopheSIAM Journal on Scientific Computing, Vol. 36 (2014), Iss. 2 P.A792
https://doi.org/10.1137/130935598 [Citations: 2] -
Geometric Self-Assembly of Rigid Shapes: A Simple Voronoi Approach
Larsson, Lisa J. | Choksi, Rustum | Nave, Jean-ChristopheSIAM Journal on Applied Mathematics, Vol. 76 (2016), Iss. 3 P.1101
https://doi.org/10.1137/15M1034167 [Citations: 1] -
Crowd distribution and location preference
Li, Weizi | Di, Zichao | Allbeck, Jan M.Computer Animation and Virtual Worlds, Vol. 23 (2012), Iss. 3-4 P.343
https://doi.org/10.1002/cav.1447 [Citations: 9] -
Pointwise Convergence of the Lloyd I Algorithm in Higher Dimension
Pagès, Gilles | Yu, JunSIAM Journal on Control and Optimization, Vol. 54 (2016), Iss. 5 P.2354
https://doi.org/10.1137/151005622 [Citations: 11]