4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Out of curiosity, what is this distance for? Does it have to do with color? $\endgroup$ – Tsuyoshi Ito Sep 1 '11 at 12:57
  • 1
    $\begingroup$ precisely ! It shall reflect the human perception of closeness of colors (such a function is of course always an approximation) $\endgroup$ – steffen Sep 1 '11 at 13:56
  • $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Sep 1 '11 at 14:46
6
$\begingroup$

First of all, I'm not sure why you even need a kd-tree for 3D data. Any reasonable grid structure will be ok to find near neighbors (See the work by Franklin for example, on spiral search methods). Secondly, the triangle inequality is needed to prune the search space correctly, so without it things will run a lot slower.

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.

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