A path from s to t on a polyhedral terrain is descending if the height of a point p never increases while we move p along the path from s to t. No ecient algorithm is known to find a shortest descending path (SDP) from s to t in a polyhedral terrain. We give a simple approximation algorithm that solves the SDP problem on general terrains. Our algorithm discretizes the terrain with O(n 2 X †) Steiner points so that after an O ‡ n 2 X † log i nX
One generalization of the Weighted Region Problem is finding a shortest aniso-tropic path @cite_18 , where the weight assigned to a region depends on the direction of travel. The weights in this problem capture, for example, the effect the gravity and friction on a vehicle moving on a slope. @cite_12 , Sun and Reif @cite_16 and Sun and Bu @cite_0 solved this problem by placing Steiner points along the edges.
@cite_0 @cite_18 @cite_16 @cite_12
1480698831 2050710547 2147998016 1989723858
We discuss the problem of computing shortest anisotropic paths on terrains. Anisotropic path costs take into account the length of the path traveled, possibly weighted, and the direction of travel along the faces of the terrain. Considering faces to be weighted has added realism to the study of (pure) Euclidean shortest paths. Parameters such as the varied nature of the terrain, friction, or slope of each face, can be captured via face weights. Anisotropic paths add further realism by taking into consideration the direction of travel on each face thereby e.g., eliminating paths that are too steep for vehicles to travel and preventing the vehicles from turning over. Prior to this work an O(nn) time algorithm had been presented for computing anisotropic paths. Here we present the first polynomial time approximation algorithm for computing shortest anisotropic paths. Our algorithm is simple to implement and allows for the computation of shortest anisotropic paths within a desired accuracy. Our result addresses the corresponding problem posed in [12]. The authors address anisotropic friction and gravity effects as well as ranges of impermissible-traversal headings due to overturn danger or power limitations. The method does not require imposition of a uniform grid, nor does it average effects in different directions, but reasons about a polyhedral approximation of terrain. It reduces the problem to a finite but provably optimal set of possibilities and then uses A* search to find the cost-optimal path. However, the possibilities are not physical locations but path subspaces. The method also exploits the insight that there are only four ways to optimally traverse an anisotropic homogeneous region: (1) straight across without braking, which is the standard isotropic-weighted-region traversal; (2) straight across without braking but as close as possible to a desired impermissible heading; (3) making impermissibility-avoiding switchbacks on the path across a region; and (4) straight across with braking. The authors prove specific optimality criteria for transitions on the boundaries of regions for each combination of traversal types. > We consider a rectilinear shortest path problem among weighted obstacles. Instead of restricting a path to totally avoid obstacles we allow a path to pass through them at extra costs. The extra costs are represented by the weights of the obstacles. We aim to find a shortest rectilinear path between two distinguished points among a set of weighted obstacles. The unweighted case is a special case of this problem when the weight of each obstacle is +∞. By using a graph-theoretical approach, we obtain two algorithms which run in O(n log2 n) time and O(n log n) space and in O(n log3 2 n) time and space, respectively, where n is the number of the vertices of the obstacles. The problem of determining shortest paths through a weighted planar polygonal subdivision with n vertices is considered. Distances are measured according to a weighted Euclidean metric: The length of a path is defined to be the weighted sum of (Euclidean) lengths of the subpaths within each region. An algorithm that constructs a (restricted) “shortest path map” with respect to a given source point is presented. The output is a partitioning of each edge of the subdivion into intervals of e-optimality, allowing an e-optimal path to be traced from the source to any query point along any edge. The algorithm runs in worst-case time O ( ES ) and requires O ( E ) space, where E is the number of “events” in our algorithm and S is the time it takes to run a numerical search procedure. In the worst case, E is bounded above by O ( n 4 ) (and we give an O( n 4 ) lower bound), but it is likeky that E will be much smaller in practice. We also show that S is bounded by O ( n 4 L ), where L is the precision of the problem instance (including the number of bits in the user-specified tolerance e). Again, the value of S should be smaller in practice. The algorithm applies the “continuous Dijkstra” paradigm and exploits the fact that shortest paths obey Snell's Law of Refraction at region boundaries, a local optimaly property of shortest paths that is well known from the analogous optics model. The algorithm generalizes to the multi-source case to compute Voronoi diagrams.