8
$\begingroup$

Given a finite set $S$ of points in $\mathbb R^d$, how can we efficiently compute a "most isolated point" $x\in S$?

We define a "most isolated point" $x$ by

$$x = \arg\max_{p \in S} \min_{q \in S \setminus \{p\}} d(p,q)$$

(I used the $x=\arg\min$ notation even though it is not necessarily unique. Here $d$ denotes the euclidean distance.) So in other words we're looking for a point with the largest distance to the closest neighbour.

A naive algorithm would be computing all pairwise distances, finding the neighbour with the least distance for every point and then finding the maximum of these. This is takes $O(n^2)$ operations, but can we do better than that?

$\endgroup$
  • $\begingroup$ I suggest looking at data structures for nearest neighbor search. I suspect they can be adapted to help solve this problem more efficiently than the naive method. $\endgroup$ – D.W. Mar 16 '18 at 16:28
  • $\begingroup$ @D.W. Thanks for the recommendation. I tried looking into kd-trees, but I did not find a more efficient way to solve this problem. $\endgroup$ – flawr Mar 16 '18 at 21:20
1
$\begingroup$

Use any algorithm for all nearest neighbors; then you can trivially solve your problem. Such an algorithm finds, for each data point, its nearest neighbor. The most isolated point is the one whose nearest neighbor is farthest away, so once you've solved all nearest neighbors, you can find the most isolated point by a simple linear scan.

Apparently all nearest neighbors can be found in $O(n \log n)$ time; see the references on Wikipedia. Or, if you want something to implement, take any data structure for nearest neighbors, and for each point $p$, find its nearest neighbor.

$\endgroup$
0
$\begingroup$

As suggested in the comments I would look into nearest neighbor queries.

Doing one NN-Query per point should be in the order of $O(n* log (n))$ so it is already better than the naive solution.

You can further improve that by adding a parameter to the NN-Query that contains the nearest neighbor distance $d_{max}$ of the most isolated point that you found so far. You can then abort any NN-query as soon as it finds a point that is closer than $d_{max}$. This should speed up your search quite a bit.

Btw, people often suggest KD-Trees for NN-Search. KD-Trees are very easy to implement but in my experience consistently scale less well with higher dimensions than other trees. For $d > 10$ or so I would recommend using an R-Tree, such as R*Tree (R-Star-Tree), X-Tree or STR-loaded R-Tree, or an PH-Tree (which is more like a bitwise quadtree).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.