Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 "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 the equivalent of the $LEC$. I can assume that all point 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?

share|improve this question
add comment

migrated from math.stackexchange.com Jun 26 '13 at 18:35

This question came from our site for people studying math at any level and professionals in related fields.

1 Answer

up vote 3 down vote accepted

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.