algorithm to find a point among n points in plane to minimize the sum of distances I have an algorithm problem here. It is different from the normal Fermat Point problem or Geometric Median problem.

Given a set of $n$ points in the plane, I need to find which one can minimize the sum of distances to the rest of $n-1$ points.

Ideally I'd like to have an algorithm for any distance; but giving a nice solution for the usual Euclidean distance is also fine.

Is there any algorithm you know of run less than $O(n^2)$? 

Thank you.
Since you have to compare a sum of square roots, it is not clear/unknown if this problem is in NP. Otherwise, if you assume you can compute sum of square roots and compare them, then I am unaware of an algorithm that works in faster than quadratic time. For approximation, you can just approximate the 1-median using known algorithms in linear time, and then just take the closest point  to this center. This would give you a constant approximation. A better approximation can be had by working somewhat harder.