quasi
Posts:
12,018
Registered:
7/15/05


Re: Question: Centroid given a distance metric
Posted:
Feb 12, 2013 3:49 AM


Andrey Savov wrote > >In other words, all I can do is, given 2 points, tell the >distance between them. I'm looking for known algorithms to >locate a point that minimizes all distances between itself >and the original points.
Minimizes all distances? That makes no sense.
What you previously said and what I think you meant to say above is that you want to find a point which minimizes the sum of the squares of the distances from the point to the points of the given set.
For a general distance function, the sum of squares of the distances may have no geometric significance whatsoever, so calling a point which minimizes that sum "a centroid" is, in my opinion, a poor choice of terminology.
>Pretty sure I can prove existence and uniqueness of these >assuming only metric definition: > <http://en.wikipedia.org/wiki/Metric_(mathematics)#Definition>
Can you prove that a metric, regarded as a function from R^n x R^n > R^n, is continuous? If not, existence of the point you seek may not be guaranteed.
And even if you assume the metric is continuous, uniqueness may fail. For example, with the discrete metric where d(p,q) = 1 for all distinct points p,q, any point of the original set qualifies as a point which minimizes the sum of the squares of the distances to the set.
quasi

