scientific article; zbMATH DE number 3907791

From MaRDI portal
Publication:3685218





[For the entire collection see Zbl 0561.00020.] An algorithm is presented that finds the shortest path between two points on a polyhedral surface in \(O(n^ 5)\) time, where n is the number of vertices on the surface, thereby establishing that the problem can be solved in polynomial time. The path is confined to the surface, and shortest is defined in terms of Euclidean distance. The algorithm is an extension of methods developed by Sharir and Schorr for finding the shortest path on a convex polyhedron. We relax the convexity assumption, only requiring that the surface be orientable.




Cited in
(31)








This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3685218)