-
-
-
-
|
---- |
|
|
Qiang's research Gallery 3
Centroidal Voronoi Tessellations -
useful tools |
|
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!) ... |
| 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. |
| 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 |
|
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
|
|
A problems related to the Gersho's conjecture.
The special lattice case is solved and it is given by the truncated octahedron,
the general case remains unsolved. The generators, in this case, form a
perfect BCC lattice. Our recent experiments provided convincing evidence to its validity. We also discussed its implications in 3d tetrahedra meshing as there is no regular tetrahedra tessellation of the 3d space. We note that the optimal 3D CVT cell corresponds to a perfect triangulation made up a subdivision-invariant, space filling tetrahedra with four shorter edges and two longer edges. Such a 3d triangulation can be viewed as an optimal triangulation. Naturally, there are also higher dimensional cases (>3) to be considered. |
 
|
| The 1d version is proved in our paper under positive density assumption. Partial resuls are obtained in higher dimenional cases were given there too. A counter-example has been provided by Vance Faber for the case of 1-d degenerate density. General case with positive density remains unsolved. |
Contact Qiang Du 2003-04-08
