Although this answers none of the OP's questions—and is in fact entirely tangential—some might enjoy this image from an earlier MO question, Delaunay triangulations and convex hulls:
![VD on sphere][1]
Image from a [Mathematica demonstration project](http://demonstrations.wolfram.com/VoronoiDiagramOnASphere/) written by Maxim Rytin.