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.
Recommendations
Cited in
(31)- Shortest descending paths through given faces
- Total curvature and spiralling shortest paths
- Shortest path on a non-convex polyhedron
- Voronoi diagrams with barriers and on polyhedra for minimal path planning
- Finding globally shortest paths through a sequence of adjacent triangles by the method of orienting curves
- Solving the shortest path problem on curved surfaces based on the simulated annealing algorithm
- Constructing a minimum path on a polyhedral surface in R^3
- The Discrete Geodesic Problem
- Shortest path algorithm for some graphs before and after folding
- Shortest Path Problems on a Polyhedral Surface
- The Number of Shortest Paths on the Surface of a Polyhedron
- On Shortest Paths in Polyhedral Spaces
- On the shortest paths between two convex polyhedra
- Finding all shortest path edge sequences on a convex polyhedron
- scientific article; zbMATH DE number 1225263 (Why is no real title available?)
- COMPUTING SHORTEST PATHS ON POLYHEDRA: APPLICATIONS IN GEOMETRIC MODELING AND SCIENTIFIC VISUALIZATION
- scientific article; zbMATH DE number 727953 (Why is no real title available?)
- Finding shortest paths in a sequence of triangles in 3D by the method of orienting curves
- Shortest path problems on a polyhedral surface
- SHORTEST PATHS ON A POLYHEDRON, Part I: COMPUTING SHORTEST PATHS
- Shortest paths on cubes
- A polynomial time algorithm to compute geodesics in CAT(0) cubical complexes
- scientific article; zbMATH DE number 7151640 (Why is no real title available?)
- Shortest paths on polyhedral surfaces and terrains
- Finding closed quasigeodesics on convex polyhedra
- Efficiently determining a locally exact shortest path on polyhedral surfaces
- A survey of geodesic paths on 3D surfaces
- Shortest paths in portalgons
- The funnel tree algorithm for finding shortest paths on polyhedral surfaces
- Shortest polygonal paths in space
- An optimal-time algorithm for shortest paths on realistic polyhedra
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)