Algorithms for the Shortest Path Between Two Arbitrary Points on a Polyhedral Surface

Three algorithms are presented for computing the shortest path between two arbitrary points on a polyhedral surface: One is an approximate algorithm; the other two can obtain the shortest path or an approximately shortest path. The approximate algorithm is to adopt a method for which the broken lines are constantly embedded in a series of triangles, whereas the other two are to find a series of triangles by using a specific normal line, and these triangles are rotated onto the same plane so as to obtain the shortest path. The time complexity of the former is O（n）, but the time complexities of the latter two are O（n²） and lower than O（2ⁿn²） respectively.