[1] 
M. Balasubramanian, J. R. Polimeni, and E. L. Schwartz.
Exact geodesics and shortest paths on polyhedral surfaces.
IEEE Transactions on Pattern Analysis and Artificial
Intelligence (PAMI), 31(6):100610016, 2009. BibTeX entry, Available here
We present two algorithms for computing distances along convex and nonconvex polyhedral surfaces. The first algorithm computes exact minimalgeodesic distances and the second algorithm combines these distances to compute exact shortestpath distances along the surface. Both algorithms have been extended to compute the exact minimalgeodesic paths and shortest paths. These algorithms have been implemented and validated on surfaces for which the correct solutions are known, in order to verify the accuracy and to measure the runtime performance, which is cubic or less for each algorithm. The exactdistance computations carried out by these algorithms are feasible for largescale surfaces containing tens of thousands of vertices, and are a necessary component of nearisometric surface flattening methods that accurately transform curved manifolds into flat representations.
