Volume 5, Issue 2
Truncated Newton-Based Multigrid Algorithm for Centroidal Voronoi Diagram Calculation

Zichao Di, Maria Emelianenko & Stephen Nash

Numer. Math. Theor. Meth. Appl., 5 (2012), pp. 242-259.

Published online: 2012-05

Preview Full PDF 37 1040
Export citation
  • 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.

  • Keywords

Centroidal Voronoi tessellation optimal quantization truncated Newton method Lloyd's algorithm multilevel method uniform convergence

  • AMS Subject Headings

15A12 65F10 65F15

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@Article{NMTMA-5-242, author = {Zichao Di, Maria Emelianenko and Stephen Nash}, title = {Truncated Newton-Based Multigrid Algorithm for Centroidal Voronoi Diagram Calculation}, journal = {Numerical Mathematics: Theory, Methods and Applications}, year = {2012}, volume = {5}, number = {2}, pages = {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.

}, issn = {2079-7338}, doi = {https://doi.org/10.4208/nmtma.2012.m1046}, url = {http://global-sci.org/intro/article_detail/nmtma/5937.html} }
TY - JOUR T1 - Truncated Newton-Based Multigrid Algorithm for Centroidal Voronoi Diagram Calculation AU - Zichao Di, Maria Emelianenko & Stephen Nash JO - Numerical Mathematics: Theory, Methods and Applications VL - 2 SP - 242 EP - 259 PY - 2012 DA - 2012/05 SN - 5 DO - http://dor.org/10.4208/nmtma.2012.m1046 UR - https://global-sci.org/intro/article_detail/nmtma/5937.html KW - Centroidal Voronoi tessellation KW - optimal quantization KW - truncated Newton method KW - Lloyd's algorithm KW - multilevel method KW - uniform convergence AB -

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.

Zichao Di, Maria Emelianenko & Stephen Nash. (1970). Truncated Newton-Based Multigrid Algorithm for Centroidal Voronoi Diagram Calculation. Numerical Mathematics: Theory, Methods and Applications. 5 (2). 242-259. doi:10.4208/nmtma.2012.m1046
Copy to clipboard
The citation has been copied to your clipboard