This Demonstration partitions the surface of a cylinder, cone, Möbius strip, sphere, or torus into Voronoi cells based on a set of up to 24 random points (sites) uniformly distributed over the surface.
You can choose from three different distance functions (Euclidean, Manhattan, or chessboard). You can choose the cell colors according to eight color schemes.
The regions are created using Mathematica's built-in function ParametricPlot3D. NearestFunction using the selected DistanceFunction is used as a MeshFunction to partition the regions into Voronoi cells.