### The weighted region problem: finding shortest paths through a weighted planar subdivisionThe weighted region problem: finding shortest paths through a weighted planar subdivision

Access Restriction
Subscribed

 Author Mitchell, Joseph S B ♦ Papadimitriou, Christos H. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1991 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Dijkstra's algorithm ♦ Voronoi diagrams ♦ Shortest paths ♦ Terrain navigation ♦ Weighted distance functions Abstract The problem of determining shortest paths through a weighted planar polygonal subdivision with $\textit{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 ε-optimality, allowing an ε-optimal path to be traced from the source to any query point along any edge. The algorithm runs in worst-case time $\textit{O}(\textit{ES})$ and requires $\textit{O}(\textit{E})$ space, where $\textit{E}$ is the number of “events” in our algorithm and $\textit{S}$ is the time it takes to run a numerical search procedure. In the worst case, $\textit{E}$ is bounded above by $\textit{O}(\textit{n}4)$ (and we give an &OHgr;(n4) lower bound), but it is likeky that $\textit{E}$ will be much smaller in practice. We also show that $\textit{S}$ is bounded by $\textit{O}(\textit{n}4\textit{L}),$ where $\textit{L}$ is the precision of the problem instance (including the number of bits in the user-specified tolerance ε). Again, the value of $\textit{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. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1991-01-03 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 38 Issue Number 1 Page Count 56 Starting Page 18 Ending Page 73

#### Open content in new tab

Source: ACM Digital Library