“Improving Chen & Han’s Algorithm on the Discrete Geodesic Problem” by Xin and Wang

The computation of geodesic distances or paths between two points on triangulated meshes is a common operation in many computer graphics applications. In this article, we present an exact algorithm for the single-source all-vertices shortest path problem.

Mitchell et al. [1987] proposed an O(n² log n) method (MMP), based on Dijkstra’s algorithm, where n is the complexity of the polyhedral surface. Then, Chen and Han [1990] (CH) improved the running time to O(n²). Interestingly Surazhsky et al. [2005] provided experimental evidence demonstrating that the MMP algorithm runs many times faster, in practice, than the CH algorithm.

The CH algorithm encodes the structure of the set of shortest paths using a set of windows on the edges of the polyhedron. Our experiments showed that in many examples over 99% of the windows created by the CH algorithm are of no use to define a shortest path. So this article proposes to improve the CH algorithm by two separate techniques. One is to filter out useless windows using the current estimates of the distances to the vertices, the other is to maintain a priority queue like that achieved in Dijkstra’s algorithm. Our experimental results suggest that the improved CH algorithm, in spite of an O(n² log n) asymptotic time complexity, greatly outperforms the original CH algorithm in both time and space. Furthermore, it generally runs faster than the MMP algorithm and uses considerably less space.

1. Agarwal, P. K., Aronov, B., O’Rourke, J., and Schevon, C. A. 1997a. Star unfolding of a polytope with applications. SIAM J. Comput. 26, 6, 1689–1713. 
2. Agarwal, P. K., Har-Peled, S., and Karia, M. 2000. Computing approximate shortest paths on convex polytopes. In Proceedings of the Symposium on Computational Geometry. 270–279. 
3. Agarwal, P. K., Har-Peled, S., Sharir, M., and Varadarajan, K. R. 1997b. Approximating shortest paths on a convex polytope in three dimensions. J. Assoc. Comput. Mach. 44, 567–584. 
4. Aleksandrov, L., Maheshwari, A., and Sack, J.-R. 2003. An improved approximation algorithm for computing geometric shortest paths. In Proceedings of Foundations of Computation Theory (FCT). 246–257.
5. Chen, J. and Han, Y. 1990. Shortest paths on a polyhedron. In Proceedings of the 6th Annual Symposium on Computational Geometry (SCG). ACM Press, New York, 360–369. 
6. Dijkstra, E. 1959. A note on two problems in connection with graphs. Numerische Mathematik 1, 269–271.
7. Har-Peled, S. 1999a. Approximate shortest paths and geodesic diameter on a convex polytope in three dimensions. Discrete Computat. Geom. 21, 2, 217–231.
8. Har-Peled, S. 1999b. Constructing approximate shortest path maps in three dimensions. SIAM J. Comput. 28, 4, 1182–1197. 
9. Hershberger, J. and Suri, S. 1995. Practical methods for approximating shortest paths on a convex polytope in r3. In Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, Philadelphia, 447–456. 
10. Kanai, T. and Suzuki, H. 2000. Approximate shortest path on polyhedral surface based on selective refinement of the discrete graph and its applications. In Proceedings of the Geometric Modeling and Processing (GMP). IEEE Computer Society, Washington, DC. 241. 
11. Kaneva, B. and O’Rourke, J. 2000. An implementation of Chen&Han’s shortest paths algorithm. In Proceedings of the 12th Canadian Conference on Computational Geometry (CCCG).
12. Kapoor, S. 1999. Efficient computation of geodesic shortest paths. In Proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC). ACM Press, New York, 770–779. 
13. Kimmel, R. and Sethian, J. 1998. Computing geodesic paths on manifolds. Proc. Nat. Acad. Sci. 95, 15, 8431–8435.
14. Mitchell, J. S. B. 2000. Geometric shortest paths and network optimization. In Handbook of Computational Geometry, J.-R. Sack and J. Urrutia, Eds. Elsevier, Chapter 15, 633–701.
15. Mitchell, J. S. B., Mount, D. M., and Papadimitriou, C. H. 1987. The discrete geodesic problem. SIAM J. Comput. 16, 4, 647–668. 
16. Mitchell, J. S. B. and Sharir, M. 2004. New results on shortest paths in three dimensions. In Proceedings of the 20th Annual Symposium on Computational Geometry (SCG). ACM Press, New York, 124–133. 
17. Morera, D. M., Velho, L., and Carvalho, P. C. 2005. Computing geodesics on triangular meshes. Comput. Graph. J. 29, 5, 667–675. 
18. Mount, D. M. 1984. On finding shortest paths on convex polyhedra. Tech. rep. 1495. Computer Science Department, University of Maryland, College Park, MD.
19. Novotni, M. and Klein, R. 2002. Computing geodesic distances on triangular meshes. In Proceedings of the 10th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision (WSCG).
20. Peyré, G. and Cohen, L. 2005. Geodesic computations for fast and accurate surface remeshing and parameterization. In Progress in Nonlinear Differential Equations and Their Applications 63, 157–171.
21. Pham-Trong, V., Szafran, N., and Biard, L. 2001. Pseudo-geodesics on three-dimensional surfaces and pseudo-geodesic meshes. Numer. Algor. 26, 4, 1017–1398.
22. Polthier, K. and Schmies, M. 2006. Straightest geodesics on polyhedral surfaces. In ACM SIGGRAPH Courses. ACM, New York, 30–38. 
23. Sander, P. V., Wood, Z. J., Gortler, S. J., Snyder, J., and Hoppe, H. 2003. Multi-chart geometry images. In Proceedings of the Eurographics/ACM SIGGRAPH Symposium on Geometry Processing (SGP). Eurographics Association, 146–155. 
24. Sethian, J. 1999. Fast marching methods. SIAM Rev. 41, 2, 199–235. 
25. Sharir, M. and Schorr, A. 1986. On shortest paths in polyhedral spaces. SIAM J. Comput. 15, 1, 193–215. 
26. Surazhsky, V., Surazhsky, T., Kirsanov, D., Gortler, S. J., and Hoppe, H. 2005. Fast exact and approximate geodesics on meshes. ACM Trans. Graph. 24, 3, 553–560. 
27. Varadarajan, K. R. and Agarwal, P. K. 1997. Approximating shortest paths on a nonconvex polyhedron. In Proceedings of the IEEE Symposium on Foundations of Computer Science. 182–191. 
28. Xin, S.-Q. and Wang, G.-J. 2007. Efficiently determining a locally exact shortest path on polyhedral surfaces. Comput.-Aid. Design 39, 12, 1113–1119. 
29. Zhou, K., Synder, J., Guo, B., and Shum, H.-Y. 2004. Iso-charts: stretch-driven mesh parameterization using spectral analysis. In Proceedings of the Eurographics/ACM SIGGRAPH Symposium on Geometry Processing (SGP). ACM Press, New York, 45–54. 
30. Zigelman, G., Kimmel, R., and Kiryati, N. 2002. Texture mapping using surface flattening via multi-dimensional scaling. IEEE Trans. Vis. Comput. Graph. 8, 1, 198–207.