A centroidal Voronoi tessellation is a Voronoi tessellation of a given set such that the associated generating points are centroids (centers of mass with respect to a given density function) of the corresponding Voronoi cells. Such tessellations are useful, in among many contexts, grid generation in volumes and surfaces, data compression, image segmentation and edge detection, optimal allocation of resources, sensor networks, music, mozaics, stippling, optimal quadrature rules, optimal representation and quantization, finite difference and finite volume schemes, cellular biology, and territorial behavior of animals. We devise and analyze methods for constructing centroidal Voronoi tessellations, analyze their theoretical properties, and use them in several applications.
Comparison of general Voronoi tessellations and centroidal Voronoi tessellations
CVT image segmentation example
CVT image compression example
Uniform and nonuniform CVTs of the sphere
Uniform and nonuniform CVTs of the surface of a torus
Adaptively refined CVT-based Delauney grid in an L-shaped region
Nonuniform CVT-based Delauney grid of the North Atlantic
Q. Du, V. Faber, and M. Gunzburger; Centroidal Voronoi tessellations: applications and algorithms, SIAM Review 41 1999, 637-676.
L. Ju, Q. Du, and M. Gunzburger; Meshless, probabilistic determination of point sets and support regions for meshless computing, Comp. Meth. Appl. Mech. Engrg. 191 2003, 1349-1366.
L. Ju, Q. Du, and M. Gunzburger; Probabilistic algorithms for centroidal Voronoi tessellations and their parallel implementation, Parallel Comput. 28 2002, 1477-1500.
Q. Du and M. Gunzburger; Grid generation and optimization based on centroidal Voronoi tessellations, Appl. Math. Comput. 133 2002, 591-607.
Q. Du and M. Gunzburger; Model reduction by proper orthogonal decomposition coupled with centroidal Voronoi tessellation, Proc. Fluids Engineering Division Summer Meeting, FEDSM2002-31051, ASME, 2002.
Q. Du, M. Gunzburger, and L. Ju; Constrained centroidal Voronoi tessellations for surfaces, SIAM J. Sci. Comput. 24 2003, 1488-1506.
V. Romero, J. Burkardt, M. Gunzburger, J. Peterson, and K. Krishnamurthy; Initial application and evaluation of a promising new sampling method for response surface generation: Centroidal Voronoi tessellations, AIAA Paper 2003-2008, Proc. 44th AIAA/AME/ASCE/AHS/ASC Structures, Structural Dynamics, and Materials Conference, AIAA, 2003.
J. Burkardt, Q. Du, M. Gunzburger, and H.-C. Lee; Reduced-order modeling of complex systems, Numerical Analysis 2003: Proceedings of the 20th Biennial Conference on Numerical Analysis, University of Dundee, Dundee, 2003, 29-38.
Q. Du, M. Gunzburger, and L. Ju; Voronoi-based finite volume methods, optimal Voronoi meshes, and PDEs on the sphere, Comp. Meth. Appl. Mech. Engrg. 192 2003, 3933-3957.
V. Romero, J. Burkardt, M. Gunzburger, and J. Peterson; Initial evaluation of centroidal Voronoi tessellation method for statistical sampling and function integration, Fourth International Symposium on Uncertainty Modeling and Analysis}, ISUMA 2003, 174-183; extended version appeared as report number SAND2003-3672C, Sandia National Laboratories, Alburquerque, 2003.
Q. Du and M. Gunzburger; Centroidal Voronoi tessellation based proper orthogonal decomposition analysis, Control and Estimation of Distributed Parameter Systems, Birkauser, Basel, 2003, 137-150.
M. Gunzburger and H.-C. Lee; Reduced-order modeling of Navier-Stokes equations via centroidal Voronoi tessellation, Recent Advances in Adaptive Computation, AMS, Providence, 2004, 213-224.
V. Romero, J. Burkardt, M. Gunzburger, and J. Peterson; Initial evaluation of pure and "latinized" centroidal Voronoi tessellation for non-uniform statistical sampling, Sensitivity Analysis of Model Output, K. Hanson and F. Hemez, eds., Los Alamos National Laboratory, Los Alamos, 2005, 380-401.
Q. Du, M. Gunzburger, L. Ju, and X. Wang; Centroidal Voronoi tessellation algorithms for image compression, segmentation, and multichannel restoration, J. Math. Imag. Vision 24 2006, 177-194.
V. Romero, J. Burkardt, M. Gunzburger, and J. Peterson; Comparison of pure and ``Latinized'' centroidal Voronoi tessellation against other statistical sampling methods, Reliab. Engrg. Sys. Safet. 91 2006, 1266-1280.
J. Burkardt, M. Gunzburger, and H.-C. Lee; Centroidal Voronoi tessellation-based reduced-order modeling of complex systems, SIAM J. Sci. Comput. 28 2006, 459-484.
J. Burkardt, M. Gunzburger, and H.-C. Lee; POD and CVT-based reduced-order modeling of Navier-Stokes flows, Comp. Meth. Appl. Mech. Engrg. 196 2006, 337-355.
L. Ju, M. Gunzburger, and W. Zhao; Adaptive finite element methods for elliptic PDEs based on conforming centroidal Voronoi-Delaynay triangulations, SIAM J. Sci. Comput. 28 2006, 2023-2053.
Y. Saka, M. Gunzburger, and J. Burkardt; Latinized, improved LHS, and CVT point sets in hypercubes, Int. J. Numer. Anal. Model. 4 2007, 729Ð743.
T. Ringler, L. Ju, and M. Gunzburger; A multi-resolution method for climate system modeling: Application of spherical centroidal Voronoi tessellations, Ocean Dyn. 56 2007, 475Ð498.
H. Nguyen, J. Burkardt, M. Gunzburger, L. Ju, and Y. Saka; Constrained CVT meshes and a comparison of triangular mesh generators, Comp. Graph. Theo. Appl. 42 2009, 1-19.
H. Nguyen, J. Burkardt, M. Gunzburger, and L. Ju; Adaptive anisotropic meshes for steady-state convection dominated equations, Comp. Meth. Appl. Mech. Engrg. 198 2009, 2964-2981.
Q. Du, M. Gunzburger, and L. Ju; Advances in studies and applications of centroidal Voronoi tessellations, to appear in Numer. Math. Theor. Meth. Appl.
Last updated: 12/29/09 by Max Gunzburger