Finding minimual spatial distance

Question

The task is to find such a dot with a (x,0) coordinates, that the distance from it to the most distant point from the original set (distance is Euclidean) is minimal. My idea is to find the minimum of the function that finds an euclidean distance like this:

import matplotlib.pyplot as plt
from scipy.spatial.distance import cdist
from scipy.optimize import minimize

def function_3(points_x, points_y):
    dots = np.array([points_x,points_y])
    ans = minimize(cdist(dots,points1),x0=0)
    return(ans)

But it seems like that I'm doing something wrong... Can somebody give an advice?

Answer 1

Solution

Here's a complete working example for fitting points of the form (x, 0):

from scipy.spatial.distance import cdist
from scipy.optimize import minimize

# set up a test set of 100 points to fit against
n = 100
xyTestset = np.random.rand(n,2)*10

def fun(x, xycomp):
        # x is a vector, assumed to be of size 1
        # cdist expects a 2D array, so we reshape xy into a 1x2 array
        xy = np.array((x[0], 0)).reshape(1, -1)
        return cdist(xy, xycomp).max()

fit = minimize(fun, x0=0, args=xyTestset)
print(fit.x)

which outputs:

[5.06807808]

This means, roughly speaking, that the minimization is finding the centroid of the set of random test points, as expected. If you wanted to do a 2D fitting to points of the form (x, y) instead, you can do:

from scipy.spatial.distance import cdist
from scipy.optimize import minimize

# set up a test set of 100 points to fit against
n = 100
xyTestset = np.random.rand(n,2)*10

def fun(x, xycomp):
        # x is a vector, assumed to be of size 2
        return cdist(x.reshape(1, -1), xycomp).max()

fit = minimize(fun, x0=(0, 0), args=xyTestset)
print(fit.x)

which outputs:

[5.21292828 5.01491085]

which, again, is roughly the centroid of the 100 random points in xyTestset, as you'd expect.

Complete explanation

The problem that you're running into is that scipy.optimize.minimize has very specific expectations about the form of its first argument fun. fun is supposed to be a function that takes x as its first argument, where x is a 1D vector of the values to be minimized over. fun can also take additional arguments. These have to be passed into minimize via the args parameter, and their values are constant (ie they won't change over the course of the minimization).

Also, you should be aware that your case of fitting (x, 0) can be simplified. It's effectively a 1D problem, so you all you need to do is calculate the x distances between the points. You can completely ignore the y distances and still get the same results.

Additionally, you don't need a minimization to solve the problem you stated. The point that minimizes the distance to the farthest point (which is the same as saying "minimizing the distance to all points") is the centroid. The coordinates of the centroid are the means of each coordinate in your set of points, so if your points are stored in an Nx2 array xydata you can calculate the centroid by just doing:

xydata.mean(axis=1)