Optimal search, finding a point where the sum of distances to other points is the smallest

Question

I have k points and I would like to find a (different) point closest to them (the sum of distances between the new point and the given points is the smallest)

On the plane for eight points

How to write a program that will get me such a point for k given points in n dimensional space (e.g 16 points in a 10-dimensional space)

How to write such a solver?

However, I would not like to use ready functions, although I will accept such a solution

Answer 1

The point for which the sum of the distances to other points is minimum is called the spatial median of these points, also called the geometric median. It can be derived by the Weiszfeld algorithm, which is implemented in the R package Gmedian.

Let's try with your example:

library(Gmedian)

X <- rbind(
  c(3, 4),
  c(5, 3),
  c(1, 8),
  c(4, 6),
  c(6, 6),
  c(0, 1),
  c(4, 6),
  c(2, 1)
)

W <- Weiszfeld(X)

---

> W
$median
         [,1]     [,2]
[1,] 3.472091 4.607492

$iter
[1] 76

Here is how you can get the sum of the distances:

smedian <- c(W$median)
sum(
  apply(X, 1, function(x){
    sqrt(crossprod(x-smedian))
  })
)
# 21.95253

As you can see, the spatial median is different than the one you got ((4,4)), and the sum of the distances is smaller than the one you got (22.84819).