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)
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). (PDF download.)
I can't resist re-sharing this image of a Vornoi diagram on a sphere from an earlier MO question:
Mathematica image by Maxim Rytin.