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. I want to improve this from O(n^2)

Now guys i've heard about Kd trees for solution, BUT KD Trees doesn't provide nearest distance if the point 'x' is already present in Kd tree. And there is no implementation for it to remove.

Edit: You can do this by ignoring self in "nearest search algo" and "where we set root/parent" initially to begin search

Answer 1

given n points Pi, 1 <= i <= n:

1. build kd-tree (with an O(n) median of median algorithm this is O(n log n))

2. for all points Pi: find second closest point (closest point will be point itself), compute distance and remember Pi if the distance is a new minimum; this is O(n log n) again.

Alltogether this is an O(n log n) algorithm.