Loading...
Please wait, while we are loading the content...
Similar Documents
Weighted Region Shortest Path Problem
| Content Provider | Semantic Scholar |
|---|---|
| Author | Reif, John H. Sun, Zheng Duke |
| Copyright Year | 1999 |
| Abstract | In this paper we present an approximation algorithm for solving the following optimal motion planning problem: Given a planar space composed of polygonal regions, each of which is associated with a positive unit weight, and two points s and t, nd a path from s to t with the minimum weight, where the weight of a path is de ned to be the weighted sum of the lengths of the sub-paths within each region. Some of the previous works on this problem involve constructing a discretization of the planar space and then computing the approximate paths in the discretized space. Discretizations used by these works include uniform and non-uniform discretizations. Our algorithm adopts discretizations proposed by previous work and presents improvement in computing optimal paths in the discretized space by using a \discretized wavefront" method. Compared to the previous work, our algorithm has the following three advantages: (a) can compute exact solutions for a discrete case of this problem; (b) can be applied to any discretization; and (c) can be applied to a more generic class of problems. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://users.cs.duke.edu/~reif/paper/sunz/weighted/weightedpath.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
