5
$\begingroup$

Given some points $X=\{x_i:||x_i||=1,i=1,\ldots,n\} $ located on the sphere, how to calculate the point $\tilde{x}$ on the sphere that is nearest to these given points. That is to say $$\tilde{x}=\arg\min_{\tilde{x}}\sum_{x_i\in X}d(\tilde{x},x_i), s.t. ||\tilde{x}||=1,$$ where $d(\tilde{x},x_i)=\arccos(\tilde{x}\cdot x_i)$ is the spherical distance between $\tilde{x}$ and $x_i$.

The question is very similar to How to calculate center point in geographic coordinates?. In that question, someone suggested to compute the mean $\bar{x}=\frac{1}{n}\sum x_i$ of the given points, and normalize the mean vector. As far as I know, the mean $\bar{x}$ is optimal under the squared L2 norm. But I am not sure that whether the normalized mean is optimal under the spherical distance measure.

Any suggestion or reference would be appreciated.

$\endgroup$
2
  • $\begingroup$ As in the flat case, the point minimizing a sum of distances need not be unique. $\endgroup$
    – hardmath
    Commented Apr 2, 2014 at 9:16
  • $\begingroup$ Yes, I just want to find one point that minimizes the sum of the distances, not all the points. @hardmath $\endgroup$
    – user139714
    Commented Apr 2, 2014 at 9:30

1 Answer 1

3
$\begingroup$

This is a problem of finding a geometric median on a sphere. While the mean provides a minimizer for the sum of squared distances (in a Euclidean setting), the $L^1$ minimum is generally not expressible in such an explicit form. For three points, the Euclidean solution is known as a Fermat point, and for four coplanar points an explicit solution is known.

The usual approach is an iterative one, using a weighted least squares minimizer while adjusting the weights to obtain the $L^1$ minimum. The basic method is called the Weiszfeld algorithm, and because of the convexity of the distance function, a suitable variant on the sphere has been conjectured to converge except for countably many initial points (though as noted, the minimizing location is not necessarily unique).

Added: Let me point out a note on the three point case by K. Ghalieh and M. Hajja, The Fermat point of a spherical triangle in The Mathematical Gazette of Nov. 1996 (pp. 561-564). Although it is "behind a pay wall", you can nonetheless take advantage of JSTOR's free-of-charge program (registration required) to read the article online (see site for details), as I have done.

The authors show that when the sides of a spherical triangle $ABC$ are sufficiently short, each less than $\pi/2$ on a sphere of unit radius (implying that they are not all on the same great circle and that no two vertices are antipodal), then a Fermat point (minimizing the sum of spherical distances to three vertices) exists, is unique, and shares some defining properties with the case of a triangle in the Euclidean plane:

  • If all three vertex angles are less than 120°, then the Fermat point $P$ is "inside" the spherical triangle (in the smaller region of the sphere bounded by the triangle) and the three sides subtend equal angles around $P$:

$$ \angle APB = \angle BPC = \angle CPA = 120° $$

  • If one of the vertex angles is 120° or more, that vertex is the Fermat point.
$\endgroup$
3
  • $\begingroup$ Thank you very much for providing the useful references. I will read them carefully. However as you mentioned, these approaches are iterative ones. I wonder whether there are analytic forms for my problem. $\endgroup$
    – user139714
    Commented Apr 3, 2014 at 12:42
  • $\begingroup$ Unfortunately I could not find sphere specific papers not behind pay walls, but I saw the other answer and hurried to get it out that the problem is studied and not trivial. If there are special circumstances that you think make the problem easier, please add them to your Question. $\endgroup$
    – hardmath
    Commented Apr 3, 2014 at 13:39
  • $\begingroup$ Regarding your third paragraph: the authors do not actually show all of these things, rather leave it to the reader. In fact they only show that the Fermat point is either a vertex or the point with equiangular property. $\endgroup$
    – Manos
    Commented Feb 28, 2016 at 18:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .