Shortest paths on a polyhedron
Jindong Chen, Yijie Han · 1990
We present an algorithm for determining the shortest path between a source point and any destination point along the surface of a polyhedron (need not be convex). Our algorithm uses a new approach which deviates from the conventional “continuous Dijkstra” technique. It takes Ο(n2) time and ⊖(n) space to determine the shortest path and to compute the inward layout which can be used to construct a structure for processing queries of shortest path from the source point to any destination point.