Most isolated point on 2d map - algorithm

Question

I have a set of points, and need to know which one has the farthest euclidean distance from any other points.

In order to get this point, I have every distance for all my points, make an average, and take the biggest average as the farthest point.

Is there any faster way to find out that point ?

Answer 1

As others have suggested, build a KD-tree for all N points. This will take O(N logN) time. For each point find the nearest neighbor, which for a single point can be done in O(logN). For all N points, you can find the most isolated point by finding the minimum of this set in O(N logN).

In addition, you now have a handy KD-tree for other distance based queries.