1990 · 72 citations · 0 references
ComputingComputer ScienceMathematicsAlgorithmsComputational GeometryGeometryConvex GeometryGeometric OptimizationGeometry ProcessingGraph AlgorithmsShortest Path AlgorithmsDijkstra's AlgorithmShortest Path ProblemsShortest Paths
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.