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).
([PDF download](http://e-lc.org/tmp/Xiaoyu__Zheng_2011_12_05_14_35_11.pdf).)

I can't resist re-sharing this image of a Vornoi diagram on a sphere from [an earlier MO question][2]:
<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
![VD on sphere][3]
<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
<sup>
[Mathematica image by Maxim Rytin](http://demonstrations.wolfram.com/VoronoiDiagramOnASphere/).
</sup>


  [1]: http://dl.acm.org/citation.cfm?id=636913
  [2]: https://mathoverflow.net/a/86438/6094
  [3]: https://i.sstatic.net/kVkgw.jpg