Significant computational resources are required when using traditional techniques for the creation of spherical centroidal Voronoi tessellations. These meshes can employ a density function that allows the creation of variable resolution spherical meshes for use in various climate models. DOE researches developed a new algorithm, featuring overlapping domain decompositions, for the parallel construction of Delaunay and Voronoi tessellations. The algorithm is then modified to employ a stereographic projection the allows parallel construction of spherical Delaunay and Voronoi tessellations. Compared to traditional approaches, this new algorithm results in significant speedups for the construction of quasi-uniform and variable resolution spherical meshes for use in new DOE climate model components.