SpringerLink
Log in

Efficient Algorithms for Geometric Shortest Path Query Problems

  • Reference work entry
  • First Online:
Handbook of Combinatorial Optimization

  • 7381 Accesses

Abstract

Computing shortest paths in a geometric environment is a fundamental topic in computational geometry and finds applications in many other areas. The problem of processing geometric shortest path queries is concerned with constructing an efficient data structure for quickly answering on-line queries for shortest paths connecting any two query points in a geometric setting. This problem is a generalization of the well-studied problem of computing a geometric shortest path connecting two specified points. This chapter covers several effective algorithmic paradigms for processing geometric shortest path queries and related problems. These general paradigms have led to efficient techniques for designing algorithms and data structures for processing a variety of queries on exact and approximate shortest paths in a number of geometric and graph-theoretic settings. Some open problems and promising directions for future research are also discussed.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 3,400.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Hardcover Book
USD 549.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Recommended Reading

  1. P.K. Agarwal, Ray shooting and other applications of spanning trees with low stabbing number. SIAM J. Comput. 21(3), 540–570 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  2. P.K. Agarwal, J. Matousek, Ray shooting and parametric search. SIAM J. Comput. 22(4), 794–806 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  3. P.K. Agarwal, M. Sharir, Applications of a new space partitioning technique. Discret. Comput. Geom. 9(1), 11–38 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  4. P.K. Agarwal, B. Aronov, J. O’Rourke, C.A. Schevon, Star unfolding of a polytope with applications. SIAM J. Comput. 26(6), 1689–1713 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  5. A. Aggarwal, J. Park, Notes on searching in multidimensional monotone arrays, in Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science, New York, 1988, pp. 497–512

    Google Scholar 

  6. A. Aggarwal, M.M. Klawe, S. Moran, P. Shor, R. Wilber, Geometric applications of a matrix searching algorithm. Algorithmica 2, 209–233 (1987)

    Article  MathSciNet  Google Scholar 

  7. O. Aichholzer, F. Aurenhammer, D.Z. Chen, D.T. Lee, E. Papadopoulou, Skew Voronoi Diagrams. Int. J. Comput. Geom. Appl. 9(3), 235–247 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  8. L. Aleksandrov, H. Djidjev, H. Guo, A. Maheshwari, D. Nussbaum, J.-R. Sack, Approximate shortest path queries on weighted polyhedral surfaces, in Proceedings of the 31st International Symposium on Mathematical Foundations of Computer Science, Stará Lesná, 2006, pp. 98–109

    Google Scholar 

  9. A. Apostolico, M.J. Atallah, L. Larmore, H.S. McFaddin, Efficient parallel algorithms for string editing and related problems. SIAM J. Comput. 19(5), 968–988 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  10. S. Arikati, D.Z. Chen, L.P. Chew, G. Das, M. Smid, C.D. Zaroliagis, Planar spanners and approximate shortest path queries among obstacles in the plane, in Proceedings of the 4th Annual European Symposium on Algorithms, Barcelona, Spain, 1996, pp. 514–528

    Google Scholar 

  11. E.M. Arkin, R. Connelly, J.S.B. Mitchell, On monotone paths among obstacles, with applications to planning assemblies, in Proceedings of the 5th Annual ACM Symposium on Computational Geometry, Saarbrüchen, 1989, pp. 334–343

    Google Scholar 

  12. E.M. Arkin, J.S.B. Mitchell, S. Suri, Optimal link path queries in a simple polygon, in Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms, Orlando, 1992, pp. 269–279

    Google Scholar 

  13. S. Arya, G. Das, D.M. Mount, J.S. Salowe, M. Smid, Euclidean spanners: short, thin, and lanky, in Proceedings of the 27th Annual ACM Symposium on Theory of Computing, Las Vegas, 1995, pp. 489–498

    Google Scholar 

  14. S. Arya, D.M. Mount, N.S. Netanyahu, R. Silverman, A. Wu, An optimal algorithm for approximate nearest neighbor searching. J. ACM 45(6), 891–923 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  15. M.J. Atallah, D.Z. Chen, Parallel rectilinear shortest paths with rectangular obstacles. Comput. Geom. 1(2), 79–113 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  16. M.J. Atallah, D.Z. Chen, On parallel rectilinear obstacle-avoiding paths. Comput. Geom. 3(6), 307–313 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  17. M.J. Atallah, D.Z. Chen, Computing the all-pairs longest chains in the plane. Int. J. Comput. Geom. Appl. 5(3), 257–271 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  18. M.J. Atallah, D.Z. Chen, Applications of a numbering scheme for polygonal obstacles in the plane, in Proceedings of the 7th Annual International Symposium on Algorithms and Computation, Osaka, Japan, 1996, pp. 1–24

    Google Scholar 

  19. M.J. Atallah, D.Z. Chen, K.S. Klenk, Parallel algorithms for longest increasing chains in the plane and related problems. Parallel Process. Lett. 9(4), 511–520 (1999)

    Article  Google Scholar 

  20. M.J. Atallah, D.Z. Chen, O. Daescu, Efficient parallel algorithms for planar st-graphs. Algorithmica 35(3), 194–215 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  21. S.W. Bae, Y. Okamoto, Querying two boundary points for shortest paths in a polygonal domain, in Proceedings of the 20th Annual International Symposium on Algorithms and Computation, Honolulu, USA, 2009, pp. 1054–1063

    Google Scholar 

  22. M. Ben-Or, Lower bounds for algebraic computation trees, in Proceedings of the 15th Annual ACM Symposium on Theory of Computing, Boston, 1983, pp. 80–86

    Google Scholar 

  23. J. Canny, J.H. Reif, New lower bound techniques for robot motion planning problems, in Proceedings of the 28th IEEE Annual Symposium on Foundations of Computer Science, Los Angeles, 1987, pp. 49–60

    Google Scholar 

  24. B. Chazelle, L.J. Guibas, Fractional cascading: I. A data structuring technique. Algorithmica 1(2), 133–162 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  25. B. Chazelle, L.J. Guibas, Fractional cascading: II. Applications. Algorithmica 1(2), 163–191 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  26. D.Z. Chen, On the all-pairs Euclidean short path problem, in Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, 1995, pp. 292–301

    Google Scholar 

  27. D.Z. Chen, Develo** algorithms and software for geometric path planning problems. ACM Comput. Surv. 28(4es) (1996) Article 18, http://www.acm.org/pubs/citations/journals/surveys/1996-28-4es/a18-chen/

  28. D.Z. Chen, Efficient algorithms for geometric shortest path query problems, in Handbook of Combinatorial Optimization, ed. by D.-Z. Du, P.M. Pardalos, vol. 2 (Kluwer Academic, Boston, 1998), pp. 1–33

    Google Scholar 

  29. D.Z. Chen, K.S. Klenk, Rectilinear short path queries among rectangular obstacles. Inf. Process. Lett. 57(6), 313–319 (1996)

    Article  MATH  Google Scholar 

  30. D.Z. Chen, O. Daescu, K.S. Klenk, On geometric path query problems. Int. J. Comput. Geom. Appl. 11(6), 617–645 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  31. D.Z. Chen, G. Das, M. Smid, Lower bounds for computing geometric spanners and approximate shortest paths. Discret. Appl. Math. 110(2–3), 151–167 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  32. D.Z. Chen, K.S. Klenk, H.-Y.T. Tu, Shortest path queries among weighted obstacles in the rectilinear plane. SIAM J. Comput. 29(4), 1223–1246 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  33. J. Chen, Y. Han, Shortest paths on a polyhedron. Int. J. Comput. Geom. Appl. 6(2) 127–144 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  34. L.P. Chew, Planar graphs and sparse graphs for efficient motion planning in the plane. Computer Science Tech. Report, PCS-TR90-146, Dartmouth College, 1987

    Google Scholar 

  35. L.P. Chew, Constrained Delaunay triangulations. Algorithmica 4(1), 97–108 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  36. L.P. Chew, There are planar graphs almost as good as the complete graph. J. Comput. Syst. Sci. 39(2), 205–219 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  37. L.P. Chew, R.L. Drysdale, Voronoi diagrams based on convex distance functions, in Proceedings of the 1st Annual ACM Symposium on Computational Geometry, Baltimore, 1985, pp. 35–244

    Google Scholar 

  38. Y.-J. Chiang, J.S.B. Mitchell, Two-point Euclidean shortest path queries in the plane, in Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, 1999, pp. 215–224

    Google Scholar 

  39. Y.-J. Chiang, F.P. Preparata, R. Tamassia, A unified approach to dynamic point location, ray shooting, and shortest paths in planar maps. SIAM J. Comput. 25(1), 207–233 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  40. J. Choi, J. Sellen, C.-K. Yap, Approximate Euclidean shortest path in 3-space. Int. J. Comput. Geom. Appl. 7(4), 271–295 (1997)

    Article  MathSciNet  Google Scholar 

  41. K.L. Clarkson, Approximation algorithms for shortest path motion planning, in Proceedings of the 19th Annual ACM Symposium on Theory of Computing, New York, 1987, pp. 56–65

    Google Scholar 

  42. K.L. Clarkson, S. Kapoor, P.M. Vaidya, Rectilinear shortest paths through polygonal obstacles in O(n(logn)2) time, in Proceedings of the 3rd Annual ACM Symposium on Computational Geometry, Waterloo, 1987, pp. 251–257.

    Google Scholar 

  43. K.L. Clarkson, S. Kapoor, P.M. Vaidya, Rectilinear shortest paths through polygonal obstacles in O(nlog3 ∕ 2 n) time, manuscript

    Google Scholar 

  44. A.F. Cook, C. Wenk, Shortest path problems on a polyhedral surface, in Proceedings of the 11th International Symposium on Algorithms and Data Structures, Banff, 2009, pp. 156–167

    Google Scholar 

  45. T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, 2nd edn. (McGraw-Hill, New York, 2001)

    MATH  Google Scholar 

  46. M. de Berg, On rectilinear link distance. Comput. Geom. 1, 13–34 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  47. M. de Berg, M. van Kreveld, M. Overmars, O. Schwartzkopf, Computational Geometry: Algorithms and Applications, 3rd edn. (Springer, Berlin, 2008)

    Google Scholar 

  48. W. Dobosiewicz, A more efficient algorithm for the min-plus multiplication. Int. J. Comput. Math. 32(1), 49–60 (1990)

    Article  MATH  Google Scholar 

  49. H. Edelsbrunner, Algorithms in Combinatorial Geometry (Springer, Heidelberg, Germany, 1987)

    Book  MATH  Google Scholar 

  50. H. ElGindy, P. Mitra, Orthogonal shortest route queries among axes parallel rectangular obstacles. Int. J. Comput. Geom. Appl. 4(1), 3–24 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  51. G.N. Frederickson, Fast algorithms for shortest paths in planar graphs, with applications. SIAM J. Comput. 16(6), 1004–1022 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  52. G.N. Frederickson, Planar graph decomposition and all pairs shortest paths. J. ACM 38(1), 162–204 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  53. M.L. Fredman, R.E. Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34(3), 596–615 (1987)

    Article  MathSciNet  Google Scholar 

  54. M.T. Goodrich, R. Tamassia, Dynamic ray shooting and shortest paths via balanced geodesic triangulations. J. Algorithms 23(1), 51–73 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  55. S. Guha, I. Suzuki, Proximity problems for points on a rectilinear plane with rectangular obstacles. Algorithmica 17(3), 281–307 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  56. L.J. Guibas, J. Hershberger, Optimal shortest path queries in a simple polygon. J. Comput. Syst. Sci. 39(2), 126–152 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  57. L.J. Guibas, J. Hershberger, D. Leven, M. Sharir, R.E. Tarjan, Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons. Algorithmica 2, 209–233 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  58. H. Guo, A. Maheshwari, J.-R. Sack, Shortest path queries in polygonal domains, in 4th International Conference on Algorithmic Aspects in Information and Management, Shanghai, 2008, pp. 200–211

    Google Scholar 

  59. S. Har-Peled, Approximate shortest paths and geodesic diameter on a convex polytope in three dimensions. Discret. Comput. Geom. 21(2), 217–231 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  60. S. Har-Peled, Constructing approximate shortest path maps in three dimensions. SIAM J. Comput. 28(4), 1182–1197 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  61. D. Harel, R.E. Tarjan, Fast algorithms for finding nearest common ancestors. SIAM J. Comput. 13(2), 338–355 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  62. J. Hershberger, A new data structure for shortest path queries in a simple polygon. Inf. Process. Lett. 38(5), 231–235 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  63. J. Hershberger, S. Suri, An optimal algorithm for Euclidean shortest paths in the plane. SIAM J. Comput. 28(6), 2215–2256 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  64. X. Hu, D.Z. Chen, R. Sambandam, Efficient list-approximation techniques for floorplan area minimization. ACM Trans. Design Autom. Electron. Syst. 6(3), 372–400 (2001)

    Article  Google Scholar 

  65. M. Iwai, H. Suzuki, T. Nishizeki, Shortest path algorithm in the plane with rectilinear polygonal obstacles (in Japanese), in Proceedings of the SIGAL Workshop, Ryukoku University, Japan, 1994

    Google Scholar 

  66. P.N. Klein, S. Rao, M. Rauch, S. Subramanian, Faster shortest-path algorithms for planar graphs. J. Comput. Syst. Sci. 55(1), 3–23 (1997)

    Article  MATH  Google Scholar 

  67. D.T. Lee, C.D. Yang, T.H. Chen, Shortest rectilinear paths among weighted obstacles. Int. J. Comput. Geom. Appl. 1(2), 109–124 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  68. D.T. Lee, C.D. Yang, C.K. Wong, Rectilinear paths among rectilinear obstacles. Discret. Appl. Math. 70(3), 185–215 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  69. R.J. Lipton, R.E. Tarjan, A separator theorem for planar graphs. SIAM J. Appl. Math. 36(2), 177–189 (1979)

    Article  MathSciNet  MATH  Google Scholar 

  70. K. Mehlhorn, A faster approximation algorithm for the Steiner problem in graphs. Inf. Process. Lett. 27(3), 125–128 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  71. J.S.B. Mitchell, An optimal algorithm for shortest rectilinear paths among obstacles, in Proceedings of the 1st Canadian Conference on Computational Geometry, Montreal, Canada, 1989

    Google Scholar 

  72. J.S.B. Mitchell, L 1 shortest paths among polygonal obstacles in the plane. Algorithmica 8(1), 55–88 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  73. J.S.B. Mitchell, Shortest paths among obstacles in the plane. Int. J. Comput. Geom. Appl. 63, 309–332 (1996)

    Article  Google Scholar 

  74. J.S.B. Mitchell, Geometric shortest paths and network optimization, in Handbook of Computational Geometry, ed. by J.-R. Sack, J. Urrutia (Elsevier Science, Amsterdam, 1998), pp. 635–701

    Google Scholar 

  75. J.S.B. Mitchell, Shortest paths and networks, in Handbook of Discrete and Computational Geometry, 2nd edn. ed. by J.E. Goodman, J. O’Rourke (CRC, Boca Raton, 2004), pp. 607–641

    Google Scholar 

  76. J.S.B. Mitchell, D.M. Mount, and C.H. Papadimitriou, The discrete geodesic problem. SIAM J. Comput. 16(4), 647–668 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  77. J.S.B. Mitchell, S. Suri, Geometric algorithms, in Network Models, ed. by M.O. Ball, T.L. Magnanti, C.L. Monma, G.L. Nemhauser. Handbook of Operations Research/Management Science (Elsevier, Amsterdam, 1995), pp. 425–479

    Chapter  Google Scholar 

  78. J.S.B. Mitchell, G. Rote, G. Woeginger, Minimum-link paths among obstacles in the plane. Algorithmica 8(5–6), 431–459 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  79. P. Mitra, B. Bhattacharya, Efficient approximation shortest-path queries among isothetic rectangular obstacles, in Proceedings of the 3rd Workshop on Algorithms and Data Structures, Montréal, 1993, pp. 518–529

    Google Scholar 

  80. K. Mulmuley, Computational Geometry: An Introduction Through Randomized Algorithms (Prentice Hall, New York, 1993)

    MATH  Google Scholar 

  81. C.H. Papadimitriou, An algorithm for shortest-path motion in three dimensions. Inf. Process. Lett. 20(5), 259–263 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  82. M. Pocchiola, G. Vegter, Topologically swee** visibility complexes via pseudotriangulations. Discret. Comput. Geom. 16(4), 419–453 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  83. M. Pocchiola, G. Vegter, The visibility complex. Int. J. Comput. Geom. Appl. 6(3), 279–308 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  84. F.P. Preparata, M.I. Shamos, Computational Geometry: An Introduction (Springer, Berlin, 1985)

    Book  Google Scholar 

  85. B. Schieber, U. Vishkin, On finding lowest common ancestors: simplification and parallelization. SIAM J. Comput. 17(6), 1253–1262 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  86. Y. Schreiber, M. Sharir, An optimal-time algorithm for shortest paths on a convex polytope in three dimensions. Discret. Comput. Geom. 39(1–3), 500–579 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  87. S. Schuierer, An optimal data structure for shortest rectilinear path queries in a simple rectilinear polygon. Int. J. Comput Geom. Appl. 6(2), 205–225 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  88. M. Sharir, P.K. Agarwal, Davenport-Schinzel Sequences and Their Geometric Applications (Cambridge University Press, New York, 1995)

    MATH  Google Scholar 

  89. P. Widmayer, Y.F. Wu, C.K. Wong, On some distance problems in fixed orientations. SIAM J. Comput. 16(4) 728–746 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  90. C.D. Yang, D.T. Lee, C.K. Wong, Rectilinear path problems among rectilinear obstacles revisited. SIAM J. Comput. 24(3), 457–472 (1995)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

The work of the author was supported in part by the National Science Foundation under Grant CCF-0916606 and Grant CCF-1217906.

Author information

Authors and Affiliations

  1. Department of Computer Science and Engineering, University of Notre Dame, 46556, Notre Dame, IN, USA

    Danny Z. Chen

Authors
  1. Danny Z. Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Danny Z. Chen .

Editor information

Editors and Affiliations

  1. Department of Industrial and Systems Eng, University of Florida, Gainesville, Florida, USA

    Panos M. Pardalos

  2. Department of Computer Science, University of Texas, Dallas, Richardson, Texas, USA

    Ding-Zhu Du

  3. Dept. Comp. Sci. & Engineering, University of California, San Diego, La Jolla, California, USA

    Ronald L. Graham

Rights and permissions

Reprints and permissions

Copyright information

© 2013 Springer Science+Business Media New York

About this entry

Cite this entry

Chen, D.Z. (2013). Efficient Algorithms for Geometric Shortest Path Query Problems. In: Pardalos, P., Du, DZ., Graham, R. (eds) Handbook of Combinatorial Optimization. Springer, New York, NY. https://doi.org/10.1007/978-1-4419-7997-1_47

Download citation

Publish with us

Policies and ethics

Search

Navigation