<p>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 <a href="http://www.ecse.rpi.edu/Homepages/wrf/pmwiki/" rel="nofollow">the work by Franklin</a> 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. </p>

<p>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 &lt; 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. </p>

CC BY-SA 3.0
2011-09-01T16:38:00.303Z
2011-09-01T16:38:00.303Z
Suresh Venkat
<p>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:</p>

<p>$x,y \in [0,255]^3$</p>

<p>$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}$</p>

<p>My question now is: </p>

<p>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.</p>

CC BY-SA 3.0
2011-09-01T13:56:34.623Z
precisely ! It shall reflect the human perception of closeness of colors (such a function is of course always an approximation)
steffen
CC BY-SA 3.0
2011-09-01T14:46:00.220Z
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
CC BY-SA 3.0
2011-09-01T12:57:38.353Z
Out of curiosity, what is this distance for?  Does it have to do with color?
Tsuyoshi Ito
<ds.data-structures><cg.comp-geom><near-neighbors>
Does kd tree requires triangular inequality for finding k-nearest neighbors
steffen
# Does kd tree requires triangular inequality for finding k-nearest neighbors

(Asked by: username_0 on 2011-09-01)

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.

**Tags:** ds.data-structures, cg.comp-geom, near-neighbors

> **Comments:**
> **username_1**: Out of curiosity, what is this distance for?  Does it have to do with color?  
> **username_0**: precisely ! It shall reflect the human perception of closeness of colors (such a function is of course always an approximation)  
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2011-09-01. Score: 6 | Accepted answer

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](http://www.ecse.rpi.edu/Homepages/wrf/pmwiki/) 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.


---

