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:

- Compute the Voronoi Diagram $VD$ of the set of points
- Compute the Convex Hull $CH$ of the set of points
- 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$. - 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?