Solve smallest circle problem in polar coordinates - that is, smallest cone

Question

I'm working on a problem relevant to astronomy. I'm looking at a few dozen stars at the same time, and I want to identify a centroid direction. Not the average, such that most stars are as close as possible, but the center of the smallest circle that encloses all of them, such that the farthest from the center is as close as possible.

I took a look at an astronomical algorithms book, and it contains a pretty nice formula for finding the smallest circle around three points, but because it is based on plane geometry, it is constricted to situations where no two stars of interest are more than 6 degrees apart. In my case, the stars are as much as 60 degrees apart, or even more, so applying plane geometry by small-angle approximation is not an option.

I've searched online, and found references to smallest-circle algorithms such as Welzl's, but those seem to be constricted to Cartesian geometry as well. I don't want a circle that is defined by a point and a distance, but a direction and an angle; I might call it a smallest cone algorithm. (Or, maybe, the smallest circle on the surface of a sphere.)

Has someone made a formula by which to identify the direction to point a telescope or camera so as to see several points simultaneously and minimize the needed field of view?

Answer 1

Off hand I would suggest that you

(1) use stereographic projection to map your points from the sphere to the plane, then

(2) apply your favorite planar algorithm for obtaining the smallest circumscribing circle, then finally

(3) apply the inverse stereographic projection to obtain the desired spherical circle.

Note that stereographic projection maps circles on the sphere to circles on the plane.

Another precautionary note: stereographic projection does not map circle centers to circle centers and of course does not preserve the size of radii. However in the generic case in which the minimum bounding circle sought passes through 3 distinct points from your data set, the stereographic projection should map the smallest bounding circle on the sphere to the smallest bounding circle on the plane.

Answer 2

Given the fact that any plane cutting through a sphere defines a circle, and all possible circles on the sphere can be obtained in this manner, it is relatively easy to modify Welzl's algorithm for the plane to apply to the sphere. All that needs to be taken care of is the cases for $|R|=1,2,3$ , when the set only contains one, two or three points.

For $|R|=1,$ the function should return the trivial circle.

For $|R|=2$, there is a unique minimal circle, whose spherical radius and center (for a unit sphere) are given by the equations

$$\cos \rho=\sqrt{\frac{1+r_1\cdot r_2}{2}}\\\hat{n}_c=\sqrt{\frac{2}{1+r_1\cdot r_2}}\left(r_1+\frac{r_2-(r_1\cdot r_2)r_1}{1+r_1\cdot r_2}\right)$$

where $r_1,r_2$ are the vectors of the positions of the two points expressed in spherical coordinates centered on the center of the sphere. Note here that the radius of the circle is exactly equal to the angle you are looking for.

Finally, for the case where $|R|=3$, in the case the algorithm must compute the unique circle going through 3 points with coordinate vectors $r_1, r_2, r_3$, the center and spherical radius of the circle are given by

$$\hat{n}_c=\frac{(r_3-r_2)\times (r_2-r_1)}{\lVert(r_3-r_2)\times (r_2-r_1)\rVert}\\\cos\rho=\frac{(r_2\times r_3)\cdot r_1}{\lVert(r_3-r_2)\times (r_2-r_1)\rVert}$$

The rest of the algorithm should remain unchanged. This is supported by the stereographic projection equivalence presented in the other answer.