3 ms·

Yes, and additionally the problem is then not Euclidian anymore. For example the triangular inequality (distance from A to B directly is always shorter than or

Yes, and additionally the problem is then not Euclidian anymore. For example the triangular inequality (distance from A to B directly is always shorter than or equal to distance from A to B via C) does not hold. I'd guess that that will deteriorate results from this method since it relies on the Euclidian distance from the current circle to the points to be visited.

n4r9 9y ago
I don't understand why you think traveling by road breaks the triangle inequality. If the time/distance along roads from A to B is fastest via C, then just go via C...
- Filligree 9y ago
  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.

n4r9 9y ago

I don't understand why you think traveling by road breaks the triangle inequality. If the time/distance along roads from A to B is fastest via C, then just go via C...

Filligree 9y ago
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.