Tuesday, February 26, 2008

double triangle inequality

The triangle inequality is one of the properties of a distance metric d. It states that, for any x, y, and z:

d(x,y) + d(y,z) ≥ d(x,z)
A somewhat lesser-known (but easy to derive) extension of this is the double triangle inequality for squared distances:
2(d2(x,y) + d2(y,z)) ≥ d2(x,z)
I have never seen the double triangle inequality used for anything. However, I would think it would be useful, given the prevalence of squared distances in objective functions. The k-means objective, for instance, is to minimize a sum of squared distances. For problems in which the objective function involves non-squared distances, the ordinary triangle inequality is often used to prove bounds on an algorithm's performance. I'm not sure why I haven't seen similar things with the double triangle inequality and squared distances.

Also, I should point out that I'm not really a theory person, so my not having seen something provides very little evidence for the nonexistence of said thing.