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$ .