Shortest path algorithms and simplification

We run the shortest path algorithms described in http://www.cs.unc.edu/~verma/shortest_path.pdf on simplified meshes and look at the effect of simplification on the length of these shortest paths.

We consider the mesh 055_mesh.smb at two different levels of simplification: 1% and 0.5%. We then run the Dijkstra's and the MMP algorithm with A-star heuristics on these meshes. Note that the source and target can shift a little after simplification and thus cause minor changes in the length of the shortest paths.

The following is the output generated by MMP algorithm on the 1% simplified mesh

• 01percent.JPG:
  

The length of this path is 276.429. Peak memory requirement was 64 mb and it took 4.7 seconds. The input mesh was ordered using Dijkstra's method iwth A-star heuristics. Reordering took 12 secs and had a peak memory usage of 294mb. The length of the Dijkstra's shortest path was 288.88.

---

The following is the output generated by MMP algorithm on the 0.5% simplified mesh

• 005percent.JPG:
  

The length of this path is 281.83. Peak memory requirement was 28mb and it took 1.86 seconds. The input mesh was ordered using Dijkstra's method iwth A-star heuristics. Reordering took 3.2 secs and had a peak memory usage of 147mb. The length of the Dijkstra's shortest path was 291.087.

---

It can be noticed that the two paths are qualitatively and quantitavely very similar. However, it is possible that on simplification the shortest path changes qualitatively but their length will remain close.

---

-- VishalVerma - 17 Dec 2008
to top