# Does kd tree requires triangular inequality for finding k-nearest neighbors

I have 3-dimensional data I want to store in a kd-tree. Additionally I have a domain-specific distance function in this space for which I have a hard time to prove the triangular inequality. Here is the function:

$x,y \in [0,255]^3$

$r=\frac{x_1+y_1}{2}$ $dist(x,y)=\sqrt{(2+\frac{r}{256})*(x_1-y_1)^2 + 4*(x_2-y_2)^2 + (2+\frac{255-r}{256})*(x_3-y_3)^2}$

My question now is:

Do I need triangular inequality, given that all other conditions of a metric are fulfilled, for the guarantee that all k-nearest neighbors to a given point can be found.

• Out of curiosity, what is this distance for? Does it have to do with color? – Tsuyoshi Ito Sep 1 '11 at 12:57
• precisely ! It shall reflect the human perception of closeness of colors (such a function is of course always an approximation) – steffen Sep 1 '11 at 13:56
• Thanks. As a random thought by non-expert, I think that it might be possible to use k-d trees if triangle inequality is satisfied in some approximate sense, but I am not sure. – Tsuyoshi Ito Sep 1 '11 at 14:46

Finally, as a side note, the coefficients on the first and third square terms are of the form $\alpha, 5-\alpha$, where $2 \le \alpha < 3$. So what you really have is a space in which the distance is defined by a Mahalanobis distance (an affinely transformed Euclidean distance) which is almost fixed (since the coefficients vary between 2 and 3). So even if the triangle inequality is not satisfied (and it's very likely it doesn't), it will be "almost satisfied" in a way that will make near-neighbor searching entirely possible.