Most isolated point on 2d map - algorithm
algorithm, computational-geometry
Solution
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.
Problem
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 ?