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.
- 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 Scholar
- 2 ~ASANO, T., ASANO, T., GUIBAS, L., HERSHBERGER, J., AND IMAI, H. Visibility of disjoint polygons. ~Algorithmica 1 (1986), 49-63. Google ScholarDigital Library
- 3 ~BAJAJ, C., AND MOH, T.T. Generalized unfoldmgs for shortest paths in Euclidean 3-space. Int. J. ~Robot. Res., to appear. Google ScholarDigital Library
- 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 ScholarDigital Library
- 5 ~DIJKSTRA. E. W. A note on two problems in connection with graphs Num Math. 1 (1959), ~269-271.Google ScholarDigital Library
- 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 Scholar
- 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 Scholar
- 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 ScholarDigital Library
- 9 ~JONES, S T. SolGng problems involving variable terrain Part 1: A general algorithm. Byte 5, 2 ~(Feb. 1980), 58-68.Google Scholar
- 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 ScholarDigital Library
- 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 Scholar
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 14 ~LEE, D. T., AND PREPARATA, F. P. Euchdean shortest paths in the presence of rectihnear ~boundaries. Networks 14 (1984), 393-410.Google ScholarCross Ref
- 15 ~LYUSTERNIK, {. A. Shortest Pal}13: Variational Problem,s Macmillan, New York, 1964Google Scholar
- 16 ~MITCHELL, J S.B. Planning shortest paths. PhD dissertation. Dept. Oper Res., Stanford Univ., ~Stanford, Cali~, Aug. 1986.Google Scholar
- 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 Scholar
- 18 ~MITCHELL J. S.B. A new algorithm for shortest paths among obstacles m the plane. Ann. Math ~Art(~ Int, to appearGoogle Scholar
- 19 ~M1TCHH~ J. S. B An algorithmic approach to some problems in terrain navigation. Arttf Int ~37(1988), 171-201. Google ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 Scholar
- 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 ScholarDigital Library
- 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 Scholar
- 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 Scholar
- 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 Scholar
- 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 Scholar
- 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 Scholar
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 Scholar
- 32 ~SHAR1R, M., A~4D SCHORR, A. On shortest paths in polyhedral spaces. SMM J. Comput. 15, 1 ~(Feb. 1986), 193-215. Google ScholarDigital Library
- 33 ~WELZL, E. Constructing the visibdity graph for n line segments in O(n2) Ume. be Proc. Lett 20 ~(1985), 167-171.Google Scholar
Index Terms
The weighted region problem: finding shortest paths through a weighted planar subdivision
Recommendations
A Shortest Path Algorithm for Real-Weighted Undirected Graphs
We present a new scheme for computing shortest paths on real-weighted undirected graphs in the fundamental comparison-addition model. In an efficient preprocessing phase our algorithm creates a linear-size structure that facilitates single-source ...
Computing $$L_1$$ Shortest Paths Among Polygonal Obstacles in the Plane
AbstractGiven a point s and a set of h pairwise disjoint polygonal obstacles with a total of n vertices in the plane, suppose a triangulation of the space outside the obstacles is given; we present an $$O(n+h\log h)$$ time and O(n) space algorithm for ...
All-Pairs Bottleneck Paths in Vertex Weighted Graphs
Let G=(V,E,w) be a directed graph, where w:Vźź is a weight function defined on its vertices. The bottleneck weight, or the capacity, of a path is the smallest weight of a vertex on the path. For two vertices u,v the capacity from u to v, denoted by c(u,...
Comments