Querying approximate shortest paths in anisotropic regions

ABSTRACT

We present a data structure for answering approximate shortest path queries ina planar subdivision from a fixed source. Let ρ ≥ 1 be a real number.Distances in each face of this subdivision are measured by a possiblyasymmetric convex distance function whose unit disk is contained in aconcentric unit Euclidean disk, and contains a concentric Euclidean disk withradius 1/ρ. Different convex distance functions may be used for differentfaces, and obstacles are allowed. Let ε be any number strictly between 0and 1. Our data structure returns a (1+ε)approximation of the shortest path cost from the fixed source to a querydestination in O(logρn/ε) time. Afterwards, a(1+ε)-approximate shortest path can be reported in time linear in itscomplexity. The data structure uses O(ρ² n⁴/ε² log ρn/ε) space and can be built in O((ρ² n⁴)/(ε²)(log ρn/ε)²) time. Our time and space bounds do not depend onany geometric parameter of the subdivision such as the minimum angle.

REFERENCES

• 1: L. Aleksandrov, H. Djidjev, H. Guo, A. Maheshwari, D. Nussbaum, and J.-R. Sack. Approximate shortest path queries on weighted polyhedral surfaces. In Proc. 31st MFCS, 2006.
• 2: L. Aleksandrov, M. Lanthier, A. Maheshwari, and J.-R. Sack. An ε-approximation algorithm for weighted shortest path queries on polyhedral surfaces. In Proc. 14th Euro CG Barcelona, pages 19--21, 1998.
• 3: L. Aleksandrov , A. Maheshwari , J.-R. Sack, Determining approximate shortest paths on weighted polyhedral surfaces, Journal of the ACM (JACM), v.52 n.1, p.25-53, January 2005 [doi>10.1145/1044731.1044733]
• 4: S.-W. Cheng, H.-S. Na, A. Vigneron, and Y. Wang. Approximating shortest paths in anisotropic regions. In Proc. 18th annual ACM-SIAM symposium on Discrete Algorithm, 2007.
• 5: L. Paul Chew , Robert L. (Scot) Dyrsdale, III, Voronoi diagrams based on convex distance functions, Proceedings of the first annual symposium on Computational geometry, p.235-244, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323264]
• 6: Sariel Har-Peled, Constructing Approximate Shortest Path Maps in Three Dimensions, SIAM Journal on Computing, v.28 n.4, p.1182-1197, Aug. 1999 [doi>10.1137/S0097539797325223]
• 7: John Hershberger , Subhash Suri, An Optimal Algorithm for Euclidean Shortest Paths in the Plane, SIAM Journal on Computing, v.28 n.6, p.2215-2256, Dec. 1999 [doi>10.1137/S0097539795289604]
• 8: R. Klein and D. Wood. Voronoi Diagrams Based on General Metrics in the Plane. pages 281--291. Springer-Verlag London, UK, 1988.
• 9: M. Lanthier, A. Maheshwari, and J. R. Sack. Approximating Shortest Paths on Weighted Polyhedral Surfaces. Algorithmica, 30(4):527--562, 2001.
• 10: L. Ma. Bisectors and Voronoi Diagrams for Convex Distance Functions. PhD thesis, Fern Universitat Hagen, 2000.
• 11: J. Mitchell. Geometric shortest paths and network optimization. In J.-R. Sack and JUrrutia, editors, Handbook of Computational Geometry, pages 633--701. Elsevier, 2000.
• 12: Joseph S. B. Mitchell , Christos H. Papadimitriou, The weighted region problem: finding shortest paths through a weighted planar subdivision, Journal of the ACM (JACM), v.38 n.1, p.18-73, Jan. 1991 [doi>10.1145/102782.102784]
• 13: John H. Reif , Zheng Sun, Movement Planning in the Presence of Flows, Algorithmica, v.39 n.2, p.127-153, February 2004 [doi>10.1007/s00453-003-1079-5]
• 14: Zheng Sun , John H. Reif, On finding approximate optimal paths in weighted regions, Journal of Algorithms, v.58 n.1, p.1-32, January 2006 [doi>10.1016/j.jalgor.2004.07.004]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Theory

Keywords:
computational geometry, data structures, shortest path