Algorithm for Finding the Largest Empty Circle on a Sphere – Reference Request

Question

Given a set $S$ of 2D points in the plane, there are known algorithms for finding the largest empty circle ($LEC$) of the set of points.

The $LEC$ problem is stated in this way: find a $LEC$ whose center is in the closed Convex Hull of S, empty in that it contains no points in its interior, and largest in that there is no other such circle with strictly larger radius.

O'Rourke describes a simple $O(n^2)$ algorithm in his book "Computational Geometry in C" (the algorithm is attributed to G.T. Toussaint, 1983. Computing Largest Empty Circles with Location Constraints. International Journal of Parallel Programming, v12.5, pp 347-358.), the algorithm goes like this:

1. Compute the Voronoi Diagram $VD$ of the set of points
2. Compute the Convex Hull $CH$ of the set of points
3. The center of the $LEC$ is at one of the $VD$ vertexes inside the $CH$ or it is at an intersection between one of the $VD$ edges and $CH$.
4. For each candidate center compute the radius of the circle centered on it and update the maximum radius.

Now, on the plane, with $P=(P_x,P_y)$, the radius is computed with the distance $dist(P,C)=\sqrt{(P_x-C_x)^2+(P_y-C_y)^2}$ for a proper $P$.

I am interested in an algorithm for a similar problem: I have a set $S'$ of 3D points lying on a sphere of radius $R$ and I would like to find the equivalent of the $LEC$. I can assume that all points of $S'$ lie on a hemisphere.

In the sphere problem, the distances are measured by means of the great-circle distance.

With $S$ the 2D circle is the locus of points equidistant from a fixed point on the plane; with $S'$ the locus of points on the sphere equidistant (distance measured by the great-circle distance) from a fixed point on the sphere is the spherical curve usually called small circle. So instead of the largest empty circle maybe I can call what I am looking for the largest empty small-circle.

Is there any published algorithm for my problem?

Answer 1

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