kNN speed up using triangle inequality

Question

can someone explain how the triangle inequality helps speed up kNN?

I understand the general principle of the triangle inequality, however I don't see how a lower bound on $d(x_1, x_2)$ would help with computation.

Lower bound from: $$d(x_1,x_2) \ge d(x_1,x_3)-d(x_2,x_3)$$

Answer 1

Answering my own question:

assuming another point $x_4$ with $d(x_1,x_4)<d(x_1,x_3)-d(x_2,x_3)$ is known, then we know that $x_2$ is not a newest neighbor, the distance then does not need to be calculated (which can be expensive in high dimensional spaces).