#StackBounty: #computational-geometry #nearest-neighbour Is there a name for the class of distance functions that are compatible with k…

Bounty: 50

The typical nearest neighbor search implementation for k-d trees prunes branches when the distance between the target and the pivot along the current axis exceeds the smallest distance found so far. This is correct (doesn’t wrongly prune any points) for any Minkowski distance. Is there a broader class of well-known distance functions that are compatible? Formally, I think the necessary and sufficient condition is just

d(x,y) ge |x_i – y_i|

for $x, y in mathbb{R}^n$, $1 le i le n$.

Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.