On the construction of the Voronoi mesh on a sphere

A new construction of the Voronoi mesh on the sphere is presented. The main feature is that the algorithm adds points one at a time until the final Voronoi mesh is built up. By adding one point to an existing Voronoi mesh of K points, only local changes are needed to construct a Voronoi mesh of K + 1 points. This construction is particularly well suited to time-dependent problems since using information from the Voronoi mesh at the previous time step allows us to reduce the construction to O(N) operations when the two configurations are close, while the algorithm does not break down when they are far apart. Numerical experiments are presented to substantiate the O(N) operation count for a "typical" case.