Approximating shortest paths on weighted polyhedral surfaces
One common problem in computational geometry is that of computing shortest paths between two points in a constrained domain. In the context of Geographical Information Systems (GIS), terrains are often modeled as Triangular Irregular Networks (TIN) which are a special class on non-convex polyhedra. It is often necessary to compute shortest paths on the TIN surface which takes into account various weights according to the terrain features. We have developed algorithms to compute approximations of shortest paths on non-convex polyhedra in both the unweighted and weighted domain. The algorithms are based on placing Steiner points along the TIN edges and then creating a graph in which we apply Dijkstra's shortest path algorithm. For two points s and t on a non-convex polyhedral surface P, our analysis bounds the approximate weighted shortest path cost as \\Pi'(s, t)\\ less than or equal to \\Pi (s, t)\\ + W\L\, where L denotes the longest edge length of P and W denotes the largest weight of any face of P. The worst case time complexity is bounded by O (n(5)). An alternate algorithm, based on geometric spanners, is also provided and it ensures that \\Pi'(s, t)\\ less than or equal to beta(\\Pi (s, t)\\ + W\L\) for some fixed constant beta > 1, and it runs in O(n(3) log n) worst case time. We also present derailed experimental results which show that the algorithms perform much better in practice and the accuracy is near-optimal.
tin weighted shortest path euclidean shortest path polyhedron