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: