Vance Faber

Abstract. A centroidal Voronoi tessellation is a Voronoi tessellation whose generating points are the centroids (centers of mass) of the corresponding Voronoi regions. We give some applica-tions of such tessellations to problems in image compression, quadrature, finite difference methods, distribution of resources, cellular biology, statistics, and the territorial behavior of animals. We discuss methods for computing these tessellations, provide some analyses concerning both the tessellations and the methods for their determination, and, finally, present the results of some numerical experiments.

We characterize the class $CG(s)$ of matrices A for which the linear system $A{\bf x} = {\bf b}$ can be solved by an s-term conjugate gradient method. We show that, except for a few anomalies, the class $CG(s)$ consists of matrices A for which conjugate gradient methods are already known. These matrices are the Hermitian matrices, $A^ * = A$, and the matrices of the form $Ae^{i\theta} (dI + B)$, with $B^ * = - B$.

The authors give a new upper bound for the diameter $D( G )$ of a graph G in terms of the eigenvalues of the Laplacian of G. The bound is \[ D ( G ) \leq \left\lfloor \frac{\text{cosh}^{ - 1} ( n - 1 )}{\text{cosh}^{ - 1} ( \frac{\lambda _n + \lambda _2 }{\lambda _n - \lambda _2 } )} \right\rfloor + 1, \] where $0 \leq \lambda _2 \leq \cdots \leq \lambda _n $ are the eigenvalues of the Laplacian of G and where $\lfloor {} \rfloor $ is the floor function.