Return to Answer

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).

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.}

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.}

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).

I can't resist re-sharing this image of a Vornoi diagram on a sphere from an earlier MO question:
           VD on sphere http://cs.smith.edu/%7Eorourke/MathOverflow/VorDiagOnSphere.jpg

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).

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.}

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).

I can't resist re-sharing this image of a Vornoi diagram on a sphere from an earlier MO question:
           VD on sphere http://cs.smith.edu/%7Eorourke/MathOverflow/VorDiagOnSphere.jpg

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).

I can't resist re-sharing this image of a Vornoi diagram on a sphere from an earlier MO question:
           VD on sphere http://cs.smith.edu/%7Eorourke/MathOverflow/VorDiagOnSphere.jpg