Centroidal Voronoi tessellations (CVTs) have become a useful tool in many applications ranging from geometric modeling, image and data analysis, and numerical partial differential equations, to problems in physics, astrophysics, chemistry, and biology. In this paper, we briefly review the CVT concept and a few of its generalizations and well-known properties. We then present an overview of recent advances in both mathematical and computational studies and in practical applications of CVTs. Whenever possible, we  point out some outstanding issues that still need investigating.

Motivated by an animal territoriality model, we consider a centroidal Voronoi tessellation algorithm from a dynamical systems perspective. In doing so, we discuss the stability of an aligned equilibrium configuration for a rectangular domain that exhibits interesting symmetry properties. We also demonstrate the procedure for performing a center manifold reduction on the system to extract a set of coordinates which capture the long term dynamics when the system is close to a bifurcation. Bifurcations of the system restricted to the center manifold are then classified and compared to numerical results. Although we analyze a specific set-up, these methods can in principle be applied to any bifurcation point of any equilibrium for any domain.

This paper considers how to use a group of robots to sense and control a diffusion process. The diffusion process is modeled by a partial differential equation (PDE), which is a both spatially and temporally variant system. The robots can serve as mobile sensors, actuators, or both. Centroidal Voronoi Tessellations based coverage control algorithm is proposed for the cooperative sensing task. For the diffusion control problem, this paper considers spraying control via a group of networked mobile robots equipped with chemical neutralizers, known as smart mobile sprayers or actuators, in a domain of interest having static mesh sensor network for concentration sensing. This paper also introduces the information sharing and consensus strategy when using centroidal Voronoi tessellations algorithm to control a diffusion process. The information is shared not only on where to spray but also on how much to spray among the mobile actuators. Benefits from using CVT and information consensus seeking for sensing and control of a diffusion process are demonstrated in simulation results.

In this paper, we present a theoretical analysis for linear finite element superconvergent gradient recovery on Par6 mesh, the dual of which is centroidal Voronoi tessellations with the lowest energy per unit volume and is the congruent cell predicted by the three-dimensional Gersho's conjecture. We show that the linear finite element solution $u_h$ and the linear interpolation $u_I$ have superclose gradient on Par6 meshes. Consequently, the gradient recovered from the finite element solution by using the superconvergence patch recovery method is superconvergent to $\nabla u$. A numerical example is presented to verify the theoretical result.

Efficient data visualization techniques are critical for many scientific applications. Centroidal Voronoi tessellation (CVT) based algorithms offer a convenient vehicle for performing image analysis, segmentation and compression while allowing to optimize retained image quality with respect to a given metric. In experimental science with data counts following Poisson distributions, several CVT-based data tessellation algorithms have been recently developed. Although they surpass their predecessors in robustness and quality of reconstructed data, time consumption remains to be an issue due to heavy utilization of the slowly converging Lloyd iteration. This paper discusses one possible approach to accelerating data visualization algorithms. It relies on a multidimensional generalization of the optimization based multilevel algorithm for the numerical computation of the CVTs introduced in [1], where a rigorous proof of its uniform convergence has been presented in 1-dimensional setting. The multidimensional implementation employs barycentric coordinate based interpolation and maximal independent set coarsening procedures. It is shown that when coupled with bin accretion algorithm accounting for the discrete nature of the data, the algorithm outperforms Lloyd-based schemes and preserves uniform convergence with respect to the problem size. Although numerical demonstrations provided are limited to spectroscopy data analysis, the method has a context-independent setup and can potentially deliver significant speedup to other scientific and engineering applications.

We tackle the problem of constructing 2D centroidal Voronoi tessellations with constraints through an efficient and robust construction of bounded Voronoi diagrams, the pseudo-dual of the constrained Delaunay triangulation. We exploit the fact that the cells of the bounded Voronoi diagram can be obtained by clipping the ordinary ones against the constrained Delaunay edges. The clipping itself is efficiently computed by identifying for each constrained edge the (connected) set of triangles whose dual Voronoi vertices are hidden by the constraint. The resulting construction is amenable to Lloyd relaxation so as to obtain a centroidal tessellation with constraints.

Most existing applications of centroidal Voronoi tessellations (CVTs) lack consideration of the length of the cluster boundaries. In this paper we propose a new model and algorithms to produce segmentations which would minimize the total energy — a sum of the classic CVT energy and the weighted length of cluster boundaries. To distinguish it with the classic CVTs, we call it an Edge-Weighted CVT (EWCVT). The concept of EWCVT is expected to build a mathematical base for all CVT related data classifications with requirement of smoothness of the cluster boundaries. The EWCVT method is easy in implementation, fast in computation, and natural for any number of clusters.