I was thinking about having a true Voronoi diagram in the distorted version of the plane and a distorted Vornoi diagram in the sphere. I'm not sure if the result would be good enough to have all the expected properties.

I'm not even sure that it's ok to do the triangulation in the plane as described in the article, perhaps mapping the triangles in the plane to distorted triangles in the sphere may case them to be too curved.