I believe the same algorithm works. Note the remarkable fact, first understood by Kevin Brown, that the Voronoi diagram of points $P$ on a sphere is combinatorially identical to the (3D) convex hull of $P$: each face of the hull corresponds to a Voronoi vertex (and to an empty circle). This leads to an $O(n \log n)$ algorithm, as explained in this paper: > Hyeon-Suk Na, Chung-Nim Lee, Otfried Cheong, "Voronoi diagrams on the sphere." *Computational Geometry: Theory and Applications*, 23 (2002) 183–194. ([ACM link][1]) Here is a recent implementation article: > Zheng, Xiaoyu, et al. "A Plane Sweep Algorithm for the Voronoi Tessellation of the Sphere." *Electronic-Liquid Crystal Communications* [online] (2011). I can't resist re-sharing this image of a Vornoi diagram on a sphere from [an earlier MO question][2]: <br /> ![VD on sphere][3] [1]: http://dl.acm.org/citation.cfm?id=636913 [2]: http://mathoverflow.net/a/86438/6094 [3]: http://cs.smith.edu/~orourke/MathOverflow/VorDiagOnSphere.jpg