3 ms·

The triangle inequality is precisely the statement that this never happens.

• n4r9 9y ago
  You misunderstand. I'm saying that a situation such as: dist(AB): 3km dist(AC): 1km dist(CB): 1km is impossible even if those are road distances rather than Euclidean distances. If the road distance of traveling A->C->B is 2km then dist(AB) should not be greater than 2km.
  • Filligree 9y ago
    So long as you're measuring in kilometers, as the bird flies. If you're talking about the distance a car would have to drive... okay, you're correct that it'd be possible to drive through C and thereby cut down on cost, but that's somewhat besides the point. The algorithm this article is talking about assumes that all points are on an Euclidean map, and the distance between them is simply the Euclidean distance. This requires the triangle inequality to hold for straight lines, and allows optimizations based on that assumption. The inequality in itself is a weaker statement than saying the whole thing is euclidean, and I haven't read it carefully enough to be sure which is required, but any violation of it is necessarily a violation of the assumptions that make this heuristic work.
    • n4r9 9y ago
      Agreed. I was just responding to Zeebrommer's claim that the triangle inequality fails with road distances.