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

dist function will be used in anycase, i want an algo better then O(n^2) — tashfeen, Jun 04 '16 at 20:50
See: http://stackoverflow.com/questions/2736290/how-to-find-two-most-distant-points — wschella, Jun 04 '16 at 20:52
Possible duplicate of [Efficient algorithm for finding spheres farthest apart in large collection](http://stackoverflow.com/questions/2276488/efficient-algorithm-for-finding-spheres-farthest-apart-in-large-collection) — XCS, Jun 04 '16 at 21:15

coproc · Accepted Answer · 2016-06-04T21:18:14.050

1

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

build kd-tree (with an O(n) median of median algorithm this is O(n log n))
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.

edited Jun 04 '16 at 21:18

answered Jun 04 '16 at 21:15

coproc

6,027
2
20
31

What is `ld n` ? log2 ? – XCS Jun 04 '16 at 21:16
ld is the logarithm with base 2; in big O notation this is actually the same as log n (base e). – coproc Jun 04 '16 at 21:17
@coproc Are you from Germany? I saw on wikipedia `ld` is mostly used in Germany :D – XCS Jun 04 '16 at 21:18
1

@tashfeen "k-nearest" is a standard function on kd-trees; you can also modify the "nearest"-function to ignore the given point itself – coproc Jun 04 '16 at 21:21
@coproc Can you provide a link to code for k-nearest ? I couldn't find any. Or i would really appreciate if you could help me in 'ignoring itself' in nearest. – tashfeen Jun 04 '16 at 21:27

score 0 · Answer 2 · answered Jun 04 '16 at 21:02

I assume that you want to find the point that maximises the distance to the nearest neighbour. Like a small island in the south pacific being 1100 miles away from the nearest land.

Well, you should be nowhere near O (n^2). Say you have a million points. Divide the points into a 1000 x 1000 grid. To find the nearest point, you would only have to examine the nine neigbouring grids, so you are far below O (n^2). If a grid contains lots of points, they will be close together so you can remove them from the search quickly.

This solution is still `O(N^2)`. How can you make sure that the "9 neighbouring grids" don't contain all the N points? — XCS, Jun 04 '16 at 21:08

Most isolated point on 2d map - algorithm

2 Answers2