skip to main content
article
Free Access

The weighted region problem: finding shortest paths through a weighted planar subdivision

Published:03 January 1991Publication History
Skip Abstract Section

Abstract

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 within 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 subdivion 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 our algorithm and S is the time it takes to run a numerical search procedure. In the worst case, E is bounded above by O(n4) (and we give an Ω(n4) lower bound), but it is likeky that E will be much smaller in practice. We also show that S is bounded by O(n4L), 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 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 optimaly 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.

References

  1. 1 ~ALEXANDER~ R. Construction of optimal-path maps for homogeneous-cost-region path-planning ~problems. Ph.D. dissertaUon. Dept. Comput. Sci., U.S. Naval Postgraduate School, Monterey, ~Cahf., Sept. 1989.Google ScholarGoogle Scholar
  2. 2 ~ASANO, T., ASANO, T., GUIBAS, L., HERSHBERGER, J., AND IMAI, H. Visibility of disjoint polygons. ~Algorithmica 1 (1986), 49-63. Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. 3 ~BAJAJ, C., AND MOH, T.T. Generalized unfoldmgs for shortest paths in Euclidean 3-space. Int. J. ~Robot. Res., to appear. Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. 4 ~Cot LINS, G E Quantifier elimination for real closed fields by cyhndric algebraic decomposition. ~In Proceedlt gs of l/le 2nd GI Co~{eretlce otl Automata Theory and Fotmal Langua,ge, s. Lecture ~Notes m Computer Science, vol. 33. Spnnger-Verlag, Berlin, 1975, pp. 134-183. Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. 5 ~DIJKSTRA. E. W. A note on two problems in connection with graphs Num Math. 1 (1959), ~269-271.Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. 6 ~GEW~LI, L., MENG, A., MITCHELL, J. S. B., AND NTAFOS, S. Path planning in 0/1/ce weighted ~regions with apphcatlons. ORSA .I Cot~lpltll&g, to appear.Google ScholarGoogle Scholar
  7. 7 ~GHOSH, S K, AND MOUNT, m. M .An output-sensitive algonthm for computing visibility graphs. ~In Proceedings q/the 28lh IEEE Symposntm on Fozoldatums oj Computer Science (Los .Angeles, ~Cah{). IEEE, New York, 1987, pp. 11-19.Google ScholarGoogle Scholar
  8. 8 ~GUIBAS, L. J., AND STOLFI, J. Primitives for the manipulation of general subdixisions and the ~computation of Voronol diagrams. A CM Tran s Graphics 4 ( 1985 ), 74-123. Google ScholarGoogle ScholarDigital LibraryDigital Library
  9. 9 ~JONES, S T. SolGng problems involving variable terrain Part 1: A general algorithm. Byte 5, 2 ~(Feb. 1980), 58-68.Google ScholarGoogle Scholar
  10. 10 ~KAPOOR, S., AND MAHESH'&ARI, S. N Efficient algorithms for Euchdean shortest path and ~v~sibihty problems with polygonal obstacles In Proceedmg~$ oj the 4th ~4nnzta{ AC~~! Symlgo,s'zztm ~on Computational Geometry (Urbana-Champalgn, Ill., June 6-8). ACM, New York, 1988, pp. ~172-182. Google ScholarGoogle ScholarDigital LibraryDigital Library
  11. 11 ~KEIRSEV, D. M., AND MITCHELL, J. S.B. Planning strategic paths through variable terrain data. ~In Proceedmgx (? the SPIE .4ppllcatlons of ArttfiCla{ Inte/hgence, ,,ol. 485. Society of Photo-Optical ~Instrumentation Engineers, Belhngham, Wash., 1984, pp. 172-179.Google ScholarGoogle Scholar
  12. 12 ~LEE, D.T. Proximity and reachabllity in the plane Ph.D. dissertation, Rep. R-831. Dept. Electrical ~Engineering, Univ. Ilhnois at Urbana-Champaign, Urbana-Champaign, Ill., Nov. 1978. Google ScholarGoogle ScholarDigital LibraryDigital Library
  13. 13 ~LEE, P. T., CHEN, T. H., AND YANG, C.D., Shortest rectilinear paths among weighted obstacles. ~In Proceedmgs of the 6t/1 Annual ,4('1{ Sympo,~lum on Computational Geometry (Berkeley, Calif., ~June 6-8) ACM, New York, 1990, pp. 301-310. Google ScholarGoogle ScholarDigital LibraryDigital Library
  14. 14 ~LEE, D. T., AND PREPARATA, F. P. Euchdean shortest paths in the presence of rectihnear ~boundaries. Networks 14 (1984), 393-410.Google ScholarGoogle ScholarCross RefCross Ref
  15. 15 ~LYUSTERNIK, {. A. Shortest Pal}13: Variational Problem,s Macmillan, New York, 1964Google ScholarGoogle Scholar
  16. 16 ~MITCHELL, J S.B. Planning shortest paths. PhD dissertation. Dept. Oper Res., Stanford Univ., ~Stanford, Cali~, Aug. 1986.Google ScholarGoogle Scholar
  17. 17 ~MITCHELl, J. S.B. Shortest paths among obstacles, zero-cost regions, and roads Tech. Rep 764. ~School of Operations Research and Industrial Engineering, Cornell University, Ithaca, N.Y., 1987.Google ScholarGoogle Scholar
  18. 18 ~MITCHELL J. S.B. A new algorithm for shortest paths among obstacles m the plane. Ann. Math ~Art(~ Int, to appearGoogle ScholarGoogle Scholar
  19. 19 ~M1TCHH~ J. S. B An algorithmic approach to some problems in terrain navigation. Arttf Int ~37(1988), 171-201. Google ScholarGoogle ScholarDigital LibraryDigital Library
  20. 20 ~MITCHELL J. S. B., IMOUNT, D. M., AND PAPADIMITRIOU, C.n. The discrete geodesic problem. ~SL43IJ Computmg 16, 4 (Aug. 1987), 647-668. Google ScholarGoogle ScholarDigital LibraryDigital Library
  21. 21 ~MrrcHELL J. S. B., AND PAPADIMITRIOU, C.H. The weighted region problem. Tech Rep. Dept ~Oper. Res., Stanford Unix'., Stanford, Calif., 1986. Extended abstract appears in Proceedings o{the ~3rd Annual ACM Conference on Computational Geometry (Waterloo, Ontario, Canada, June ~8-10). ACM, New York, 1987, pp 30-38. Google ScholarGoogle ScholarDigital LibraryDigital Library
  22. 22 ~MrrcHEl,L, J S. B., P4YTON, D. W., AND KEIRSEY, m.M. Planning and reasoning for autonomous ~vehicle control. Int J Dire}{ Sys{ II(1987), 129-198.Google ScholarGoogle Scholar
  23. 23 ~PAP&DkKLq, IM. A., &~D PrnM~ig, &. Nl. Determmlgtie minimal hme vessel routing Opc~ }~es 3~9, ~3 (May-June 1990), 426-439. Google ScholarGoogle ScholarDigital LibraryDigital Library
  24. 24 ~PAPADAKIS, N A, AND PERAKIS, A. N. Minimal time vessel routing in a time-dependent ~environment. D'ans79ort. Set 23, 4 (Nov. 1989), 266-276.Google ScholarGoogle Scholar
  25. 25 ~QUEK, F. K. H., FRANKLIN, R. F., AND PONT, F. A decision system for autonomous robot ~navigation o~er rough terram. In Proceedmg~ of the SPIE A??/lc'atlon~ o/Artl/iclal Intdhgenee ~(Boston). Soc~et? of Photo-Optical Instrumentation Engineers, Belhngham, Wash., 1985.Google ScholarGoogle Scholar
  26. 26 ~REIF, J H., AND STORER, J.A. Shortest paths in Euclidean space with polyhedral obstacles. Tech. ~Rep. CS-85-121. Comput. Sci. Dept., Brandeis Umv. Waltham, Mass., Apr. 1985.Google ScholarGoogle Scholar
  27. 27 ~R1CHBOURG, R. F Solving a class of spatial reasoning problems: Minimal-cost path planning in ~the Cartesian plane. Ph D. d~ssertation. Dept. Comput. Sci., U S. Naval Postgraduate School, ~Monterey, Calif., June, 1987. Also issued as Tech. Rep. NPS52-87-021 and NPS52-87-022.Google ScholarGoogle Scholar
  28. 28 ~RICHBOURG, R. F, ROWE, N. C., AND ZYDA, M. J., AND MCGHEE, R., Solving global two- ~dimensional routing problems using Snell's law and ,4* search. In Proc'eedmgs of the 1EEE ~International Conference on Robotws and Automation (Raleigh, N.C., Feb.). IEEE, New York, ~1987, pp. 1631-1636.Google ScholarGoogle Scholar
  29. 29 ~ROWE, N.C. Roads, rivers, and obstacles: Optimal two-dimensional path planning around hnear ~features for a mobile agent, bU. J Robot. Res. 9, 6 (Dec. 1990), 67-73. Google ScholarGoogle ScholarDigital LibraryDigital Library
  30. 30 ~ROWE, N. C., AND RICHBOURG, R.F. An efficient Snell's law method for optimal-path ptannmg ~across multiple two-dimensmnal irregular homogeneous-cost regions. Int J. Robot. Res 9, 6 (Dec. ~1990), 48-66. Google ScholarGoogle ScholarDigital LibraryDigital Library
  31. 31 ~ROWE, N. C., AND ROSS, R.S. Optimal gnd-free path planning across arbitrarily-contoured terrain ~with anisotroplc friction and gravity effects. Tech Rep. NPS52-89-003. Dept. Comput. Sc~. U.S. ~Naval Postgraduate School, Monterey, Calif., Nov. 1988. Also in IEEE J. Robot Automation, ~submitted.Google ScholarGoogle Scholar
  32. 32 ~SHAR1R, M., A~4D SCHORR, A. On shortest paths in polyhedral spaces. SMM J. Comput. 15, 1 ~(Feb. 1986), 193-215. Google ScholarGoogle ScholarDigital LibraryDigital Library
  33. 33 ~WELZL, E. Constructing the visibdity graph for n line segments in O(n2) Ume. be Proc. Lett 20 ~(1985), 167-171.Google ScholarGoogle Scholar

Index Terms

  1. The weighted region problem: finding shortest paths through a weighted planar subdivision

          Recommendations

          Reviews

          Thomas Rainer Michael Fischer

          In this generalization of the two-dimensional shortest path problem with polygonal obstacles, the plane is subdivided into polygonal regions, each of which is associated with a weight specifying the unit cost of traveling in that region. The aim is to find a path that minimizes the total cost according to a weighted Euclidean metric. The shortest path problem with obstacles is a special case of this weighted region problem in which the weights are either 1 or ? , depending on whether a region is free space or an obstacle, respectively. The authors present a polynomial-time solution to the general weighted region problem. For any polygonal subdivision with integer weights assigned to each face edge, the algorithm constructs a labeling of each vertex with the length of an optimal path from a given source to it. Moreover,<__?__Pub Caret> the algorithm allows one to find an optimal path to any query point on any edge. Here the notion of optimality is related to some given error tolerance. The paper contains an informal description of the algorithm as well as a detailed discussion of the mathematical background. The algorithmic approach is based on a continuous Dijkstra technique that was introduced in previous papers. The correctness of the algorithm is proven, and a complexity analysis, including a discussion of the numerical issues, concludes the paper.

          Access critical reviews of Computing literature here

          Become a reviewer for Computing Reviews.

          Comments

          Login options

          Check if you have access through your login credentials or your institution to get full access on this article.

          Sign in

          Full Access

          • Published in

            cover image Journal of the ACM
            Journal of the ACM  Volume 38, Issue 1
            Jan. 1991
            254 pages
            ISSN:0004-5411
            EISSN:1557-735X
            DOI:10.1145/102782
            Issue’s Table of Contents

            Copyright © 1991 ACM

            Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

            Publisher

            Association for Computing Machinery

            New York, NY, United States

            Publication History

            • Published: 3 January 1991
            Published in jacm Volume 38, Issue 1

            Permissions

            Request permissions about this article.

            Request Permissions

            Check for updates

            Qualifiers

            • article

          PDF Format

          View or Download as a PDF file.

          PDF

          eReader

          View online with eReader.

          eReader