TY - GEN
T1 - The weighted region problem
AU - Mitchell, Joseph S.B.
AU - Papadimltriou, Christos H.
N1 - Publisher Copyright:
© 1987 ACM.
PY - 1987/10/1
Y1 - 1987/10/1
N2 - We present an algorithm for determining the shortest path between a source and a destination through aplanar subdivision in which each region has an associated weight. Distances are measured according to aweighted Euclidean metric: Each region of the subdivision has associated with it a weight, and the weighteddistance between two points in a convex region is the product of the corresponding weight and the Euclideandistance between them. Our algorithm runs in time 0(n7L) and requires 0(n3) space, wheren is the number of edges of the subdivision, and L is the precision of the problem instance (including thenumber of bits in a user-specified tolerance e, which is the percentage the solution is allowed to differ froman optimal solution). The algorithm uses the fact that shortest paths obey Snell's Law of Refraction at regionboundaries, a local optimality property of shortest paths that is well-known from the analogous optics model.
AB - We present an algorithm for determining the shortest path between a source and a destination through aplanar subdivision in which each region has an associated weight. Distances are measured according to aweighted Euclidean metric: Each region of the subdivision has associated with it a weight, and the weighteddistance between two points in a convex region is the product of the corresponding weight and the Euclideandistance between them. Our algorithm runs in time 0(n7L) and requires 0(n3) space, wheren is the number of edges of the subdivision, and L is the precision of the problem instance (including thenumber of bits in a user-specified tolerance e, which is the percentage the solution is allowed to differ froman optimal solution). The algorithm uses the fact that shortest paths obey Snell's Law of Refraction at regionboundaries, a local optimality property of shortest paths that is well-known from the analogous optics model.
UR - https://www.scopus.com/pages/publications/84914897261
U2 - 10.1145/41958.41962
DO - 10.1145/41958.41962
M3 - Conference contribution
AN - SCOPUS:84914897261
T3 - Proceedings of the 3rd Annual Symposium on Computational Geometry, SCG 1987
SP - 30
EP - 38
BT - Proceedings of the 3rd Annual Symposium on Computational Geometry, SCG 1987
A2 - Soule, D.
PB - Association for Computing Machinery, Inc
T2 - 3rd Annual Symposium on Computational Geometry, SCG 1987
Y2 - 8 June 1987 through 10 June 1987
ER -