Quote:Original post by Vorpy
Bad news: I found a counterexample.
I drew it the same way as the image above. In this case it is a Delaunay triangulation, and the path found does not go through the nodes of the shortest path. The red arc makes the upper path longer than the lower path when following the triangulation, but taking the upper path and going straight across is the shortest route. Time to try proving bounds on how far from optimal the path can be?
Edit: Actually it looks like I made a mistake and surprisingly in this picture the green and red path is actually shorter than the light blue path. The counterexample still works though, some stuff needs to be nudged around a little.
This bad case happens because your discretisation of the continuous search space is too sparse. In other words, your triangles are too big for the precision you want in finding the minimum path.