Minimum bounding circle on a sphere

Question

This question is almost certainly answered elsewhere, but I am at a loss for what to search for. It's also possible that this is a question better suited for a computer science stack exchange.

The final application will be: given some set of coordinates on a sphere (i.e. the border of a country), find the minimum bounding circle on the sphere. I can imagine this is a problem that mapping software has figured out (like when you search for a country on Google Earth and it rotates the planet to perfectly center it). We can also safely assume that all of the points are contained within a hemisphere of the sphere, and in reality these points are a lot closer together than that.

I've tried to think through it logically, and I believe I'm approaching a rudimentary solution. A "circle on a sphere" is better represented by a plane's intersection with the sphere, and there are known simple algorithms for determining if a point in 3D space is above or below a plane. So we need to find the "best fit" plane where all of the points are "above" the plane, from the viewpoint of the center of the sphere. It seems most logical to define the plane in terms of the three variables, none of which can be fixed:

1. φ - latitude [0, π/2]
2. λ - longitude [-π, π]
3. h - height from center of sphere (0, r)

So when we define it in terms of these variables, we're looking for a plane with the maximum value of h. I can imagine the algorithm would iteratively look at every point, and when a point lies under the plane, it would move the plane to bring that point above it (or ON the plane), slightly widening the circle in the process. But this process of adjusting the plane is not as trivial as I originally thought, and a simple solution would not produce the minimum bounding circle.

As I said, I apologize in advance for the likely duplicate question; I'm pretty sure this is a solved problem, and I am hoping the answer is just a link to a Wikipedia article or previous answered question.

Answer 1

Use stereographic projection $P$ with center the North pole $N$ mapping any point $M$ of the unit sphere onto $P(M)=M'$ into its equatorial plane with property:

$$N,M,M' \ \text{aligned}\tag{1}$$

One of the main properties of this transformation is that circles on the sphere are mapped onto circles into the equatorial plane.

Therefore the principle is to transform the set of points $P_k$s on the sphere onto a set of points $P'_k$s on the equatorial plane, determine the smallest enclosing circle of these points, and then send it back on the sphere.

The transformation formula (1) can be given an analytical form : $$\begin{cases}x'&=&\frac{x}{1-z}\\y'&=&\frac{y}{1-z}\end{cases}$$

The inverse transform can be given the following form

$$\begin{cases}x&=&2x'/D\\y&=&2y'/D\\z&=&(-1+x^2+y^2)/D \end{cases} \ \text{with} \ D:=1+x^2+y^2$$

due to relationship:

$$\vec{NM'}=2 \dfrac{\vec{NM}}{\|NM\|^2}$$

Remark: the stereographic projection is a particular case of an inversion, i.e. , the inversion with center $N$ and power $2$.

Answer 2

The minimum bounding sphere of points in $\mathbb {R^3}$ can give the wrong answer. Consider a set of three points: the north pole, 80S 180W, and 80S 0W. the minimum bounding sphere would be the original sphere, so the intersection doesn't give you a circle. The minimum bounding circle would be the union of the two meridians at lon=0 and lon=180.