Q. Du
Qiang's research Gallery 3            

Centroidal Voronoi Tessellations -  useful tools
         for information analysis & scientific computation
             (see Qiang's publications for details)


Brief Introduction
A centroidal Voronoi tessellation (CVT) 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 regions. The pictures below gives examples of a generic Voronoi tessellation of a square and a CVT corresponding to a constant density.
We are now studying methods for computing these tessellations, the underlying mathematical theory and their applications. See Centroidal Voronoi Tessellations: Applications and Algorithms, SIAM Review, 41, p637-676, 1999 for more discussions (on the development before 2000). A list of publications is also available. Recent works include constrained CVTs (which are used in for instance, spherical CVTs) and anisotropic CVTs. CVTs have found applications in many subjects: from arts to science, from business to engineering, some examples include include mosiac design, music selection, stippling technique, computational geometry, numerical PDEs, meshfree computation, image segmentation, adaptive binning, vector field visualization, surface discretization, volume meshing, sensor placement, mobile network, particle swarm optimization, resource allocation, reduced order modeling, robot navigation, cell divisions, phyllotaxis, photonic crystal, (search google scholars!) ...

Algorithms, old and new
There are deterministic and probabilistic algorithms. For example, the classical Lloyd's methof and the MacQueen's k-means methods. We also developed parallel algorithms and analysed other algorithms. See Numerical studies of MacQueen's k-means algorithm for computing the centroidal voronoi tessellations, Computer Math Appl 44, 511-523, 2002 and also Probabilistic methods for centroidal Voronoi tessellations and their parallel implementations, Parallel Computing, 28, pp.1477-1500, 2002 for more discussions. Recently completed works include the study of global convergence of the Lloyd iterations and their multilevel accerlerations. Our paper in Parallel Computing was in the top download at Elsevier in 2003.

Applications, in particular, to Numerical PDEs
The CVTs are useful in data compression, optimal quadrature rules, optimal representation and quantization, image analysis, finite difference and volume schemes, mesh generations, optimal distribution of resources, cellular biology, and the territorial behavior of animals. A couple of examples in image analysis are shown here: CVT-based segmentation of x-ray bone tissue images

and CVT-based segmentation of simple geometric objects
Other examples can be found in gallery 4.
More applications of CVTs in computer graphics include stippling and binning techniques as well as the design of decorative mosiacs.

One particular application that we pay close attention to is the numerical solution of PDEs. For example, CVTs can help with grid generation and optimization, nodal distribution in meshfree computing, and design of discretization schemes. An example of CVT-based nodes and support regions distribution for a 2d square containing a slit is given below:

In computer graphics and also in mesh generation, it is well known that Voronoi tessellations and their dual Delaunay tessellations (formed by joining adjacent Voronoi generators) are useful tools in the construction of unstructured tetrahedral mesh. A two dimensional example is given on the right. Naturally, CVTs and their dual CVDTs (centroidal Voronoi-Dalaunay triangulations) provides even more superior mesh quality and solution resolution. Some three dimensional meshing examples are given below:
   One can also extend CVT concept to manifolds or CVTs with constraints. For example, we have studied CVTs on the sphere (SCVT) in details. In such case, the mass centers are constrained to be on the sphere. An example of spherical CVT is given by the buckyball shown on the right. SCVTs could be very useful in atomospheric and climate modeling. More computed examples of spherical CVTs with uniform & non-uniform densities are given below

One can also apply to some practical 3d meshing examples that involve conforming
or constrained boundary recovery

Our recent analysis and experiments show that The CVT based mesh provides superconvergent numerical solutions when applied to solve PDES via either finite element or finite volume methods.

Unsolved problems

Further reading
Q. Du, V. Faber and M. Gunzburger, Centroidal Voronoi Tessellations: Applications and Algorithms,
    publihsed in SIAM Review, 41, p637-676, 1999
Grid generation and optimization based on centroidal Voronoi tessellations ,
    Appl Math Comp, 133, pp591-607, 2002
Meshfree, probabilistic determination of point sets and support regions for meshless computing ,
    Computer Meth in Applied Mech Eng, 191, pp.1349-1366, 2002
Tetrahedral mesh generation and optimization based on centroidal Voronoi tessellations ,
    Inter. J. Numer. Meth. Eng., 56, No.9, pp.1355-1373, 2002.
Probabilistic methods for centroidal Voronoi tessellations and their parallel implementations ,
   Parallel Computing, 28, pp.1477-1500, 2002
Voronoi-based finite volume methods, optimal Voronoi meshes, and PDEs on the sphere ,
    Comput. Meth. Appl. Mech. Engrg. , 192, pp. 3933-3957, 2003
Numerical studies of MacQueen's k-means algorithm for computing the centroidal voronoi tessellations ,
   Computer Math Appl 44, 511-523, 2002
Constrained Centroidal Voronoi Tessellations for Surfaces ,
   SIAM J. Scientific Comp.,24, pp. 1488-1506, 2003
Anisotropic Centroidal Voronoi Tessellations and Their Applications ,
   SIAM J. Sci Comp., 26, pp. 737-761, 2005.
Boundary recovery for three dimensional conforming Delaunay triangulation ,
    Comp. Meth. Appl. Mech. Engr, 193, pp2547-2563, 2004
Constrained boundary recovery for three dimensional Delaunay triangulations ,
    Int. J. Numer. Meth. Eng., 61, pp1471-1500, 2004
Tessellation and Clustering by Mixture Models and Their Parallel Implementations,
    SIAM Data Mining Conference, 2004
Centroidal Voronoi tessellation based algorithms for vector fields visualization and segmentation,
    Proceedings of the IEEE conference on visualization, (VIS2004), pp43-50, Austin, TX, 2004.
CVT based POD analysis,
    International series of Numerical Mathematics, 143, pp.137-150, Birkhauser, 2002
The Optimal Centroidal Voronoi Tessellations and the Gersho's Conjecture in the Three Dimensional Space ,
    Computers and Mathematics with Applications, 49, pp.1355-1373, 2005.
Recent progress in robust and quality Delaunay mesh generation,
    J. Computational Applied Mathematics, 195, pp8-23, 2006
Ideal Point Distributions, Best Mode Selections and Optimal Spatial Partitions via Centroidal Voronoi Tessellations ,
   Proceedings of 2nd Inter Symposium on Voronoi Diagrams in Sciences and Engineering, Seoul, Korea, Oct, 2005
Convergence of the Lloyd Algorithm for Computing Centroidal Voronoi Tessellations,
    SIAM J. Numer. Anal., 44, pp.102-119, 2006
Acceleration of algorithms for the computation of centroidal Voronoi tessellations,
    Numerical Linear Algebra and Applications, 2005
Mesh and Solver co-adaptation,
    Numerical Methods for Partial Differential Equations, 21, pp.859-874, 2005
Mesh Optimization Based on the Centroidal Voronoi Tessellation
    International Journal of Numerical Analysis and Modeling, 2, Supp, pp.100-113, 2005,
Finite Volume Methods on Spheres and Spherical Centroidal Voronoi Meshes,
    SIAM J. Numer. Anal., 43, pp. 1673-1692, 2005.
Centroidal Voronoi Tessellation Algorithms for Image Compression, Segmentation, and Multichannel Restoration ,
    J. of Mathematical Imaging and Vision, 24, pp.177-194, 2006
Analysis of a mixed finite volume discretization of fourth-order equations on general surfaces,
    IMA Numerical Analysis, 2008.
A Finite volume methods on general surfaces and itr error estimates .
    J. Math. Ana. Appl., 352, pp.645-668, 2009
Search in Google scholar for more references

CVT, a C++ library for CVTs
CCVT_BOX, a C++ program for CVTs in a BOX

For additonal works, see Qiang's list of publications.

Collaborators: M. Emelianenko, V. Faber, M. Gunzburger, L. Ju, L. Tian, D. Wang, X. Wang, T. Wong

Contact  Qiang Du  2003-04-08