id: 00622309 dt: j an: 00622309 au: Mitchell, Joseph S.B.; Papadimitriou, Christos H. ti: The weighted region problem: Finding shortest paths through a weighted planar subdivision. so: J. Assoc. Comput. Mach. 38, No.1, 18-73 (1991). py: 1991 pu: Association for Computing Machinery (ACM), New York, NY la: EN cc: ut: nonlinear programming; shortest paths; weighted planar polygonal subdivision; Snell’s Law of Refraction; Voronoi diagrams ci: li: doi:10.1145/102782.102784 ab: Summary: 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 with 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 subdivision 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 \$O(ES)\$ and requires \$O(E)\$ space, where \$E\$ is the number of “events” in the 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\sp 4)\$ (and we give an \$Ω(n\sp 4)\$ lower bound), but it is likely that \$E\$ will be much smaller in practice. We also show that \$S\$ is bounded by \$O(n\sp 4 L)\$, where \$L\$ is the precision of the problem instance (including the number of bits in the user-specified tolerance \$ε\$). Again, the value of \$S\$ should be much 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 optimality 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. rv: