## Finite Volume Method on Spherical Voronoi Meshes

**Abstract :**
We first develop and analyze a finite volume scheme for the discretization
of partial differential equations on the sphere; the scheme uses Voronoi
tessellation of the sphere. For a model convection-diffusion problem, the
finite volume scheme is shown to produce first-order accurate approximations
with respect to a mesh-dependent discrete first-derivative norm. Then, we
introduce the notion of constrained centroidal Voronoi tessellation (CCVTs)
of the sphere; these are special Voronoi tessellation of the sphere for
which the generators of the Voronoi cells are also the constrained centers
of mass, with respect to a prescribed density function, of the cells. After
discussing an algorithm for determining CCVT meshes on the sphere, we discuss
and illustrate several desirable properties possessed by these meshes. In
particular, it is shown that CCVT meshes define very high quality uniform
and nonuniform meshes on the sphere. Finally, we discuss, through some
computational experiments, the performance of the CCVT meshes used in
conjunction with the finite volume scheme for the solution of simple model
PDEs on the sphere. The experiments show, for example, that the CCVT based
finite volume approximations are second-order accurate if errors are measured
in discrete $L^2$-norms.