Article

Free access

Path planning in 0/1/ weighted regions with applications

Authors:

J. S. Mitchell,

S. NtafosAuthors Info & Claims

SCG '88: Proceedings of the fourth annual symposium on Computational geometry

Pages 266 - 278

https://doi.org/10.1145/73393.73421

Published: 06 January 1988 Publication History

Abstract

We consider the terrain navigation problem in a two-dimensional polygonal subdivision consisting of obstacles, “free” regions (in which one can travel at no cost), and regions in which cost is proportional to distance traveled. This problem is a special case of the weighted region problem and is a generalization of the well-known planar shortest path problem in the presence of obstacles. We present an Ο(n²) exact algorithm for this problem and faster algorithms for the cases of convex free regions and/or obstacles. We generalize our algorithm to allow arbitrary weights on the edges of the subdivision. In addition, we present algorithms to solve a variety of important applications: (1) an Ο(n²W) algorithm for finding lexicographically shortest paths in weighted regions (with W different weights); (2) an Ο(k²n²) algorithm for planning least-risk paths in a simple polygon that contains k line-of-sight threats (this becomes Ο(k⁴n⁴) in polygons with holes); and (3) an Ο(k²n³) algorithm for finding least-risk watchman routes in simple rectilinear polygons (a watchman route is such that each point in the polygon is visible from at least one point along the route).

References

[1]

T. Asano, T. Asano, L. Guibas, J. Hershberger, and H. Imai, "Visibility-Polygon Search and Euclidean Shortest Paths", Proc. 26th Annum IEEE Symposium on Foundations of Computer Science, 1985.

Digital Library

[2]

T. Asano, T. Asano, and H. Imai, "Shortest Path Between Two Simple Polygons", Information Processing Letters, 24, 1987, pp. 285-288.

Digital Library

[3]

J. Canny and J. Reif, "New Lower Bound Techniques for Robot Motion Planning Problems", Proc. 28th FOCS, pp. 49-60, Oct. 1987.

Digital Library

[4]

W.P. Chin and S. Ntafos, "Optimum Watchman Routes", Information Processing Letters (To Appear); preliminary version in Proc. 2nd ACM Symposium on Computational Geometry, pp. 24- 33, 1986.

Digital Library

[5]

W.P. Chin and S. Ntafos, "Watchman Routes in Simple Polygons", Technical Report, Computer Science, University of Texas at Dallas, 1987.

[6]

H.A. El Gindy and D. Avis, "A Linear Algorithm for Computing the Visibility Polygon From a Point", Journal of Algorithms, Vol. 2 (1981), pp. 186-197.

[7]

M. Fredman and R. Tarjan, "Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms", Proc. 25th Annum IEEE Symposium on Foundations of Computer Science, pp. 338-346, 1984.

Digital Library

[8]

S.K. Ghosh and D.M. Mount, "An Output Sensitive Algorithm for Computing Visibility Graphs", Technical Report CS-TR-1874, Department of Computer Science, University of Maryland, July 1987. (Also appears in FOCS, 1987.)

Digital Library

[9]

D.T. Lee, "Proximity and Reachability in the Plane", Ph.D. Thesis, Technical Report ACT- 12, Coordinated Science Laboratory, University of Illinois, Nov. 1978.

Digital Library

[10]

D.T. Lee and Y.T. Ching, "The Power of Geometric Duality Revisited", Information Processing Letters, 21 (1985), pp. 117-122.

[11]

J.S.B. Mitchell, "Planning Shortest Paths", PhD Thesis, Department of Operations Research, Stanford University, August, 1986. (Available as Research Report 561, Artificial Intelligence Series, No. 1, Hughes Research Laboratories, Malibu, CA.)

[12]

J.S.B. Mitchell, "An Algorithmic Approach to Some Problems in Terrain Navigation", Workshop on Geometric Reasoning, Oxford University, Oxford, England, June-July 1986. To Appear: AI Journal.

Digital Library

[13]

J.S.B. Mitchell, "Shortest Paths Among Obstacles, Zero-Cost Regions, a.nd Roads", Technical R.eport, Department of Operations Research, Cotnell University, 1987.

[14]

J.:S.B. Mitchell, "On the Maximum Concealment Problem", Forthcoming TechnicM Report, Department of Operations Research, Cornell University.

[15]

J.S.B. Mitchell, "On Maximum Flows in Polyhedral Domains", These Proceedings.

Digital Library

[16]

J.S.B. Mitchell, D.M. Mount, and C.H. Papadimitriou, "The Discrete Geodesic Problem", SIAM JournM on Computing, 16, No. 4, pp. 647-668, August, 1987.

Digital Library

[17]

J.S.B. Mitchell and C.H. Papadimitriou, "The Weighted Region Problem", Technical Report, Department of Operations Research, Stanford University, 1985. (Extended abstract appears in: Ptoc. Third Annum ACM Conference on Computational Geometry, Waterloo, June 1987.)

Digital Library

[18]

J. O'Rourke, Art Gallery Theorems and Algorithms, Oxford University Press, 1987.

Digital Library

[19]

J.H. Reif and J.A. Storer, "Shortest Paths in Euclidean Space with Polyhedral Obstacles", Technical Report CS-85-121, Computer Science Department, Brandeis University, April, 1985.

[20]

H. Rohnert, "New Algorithms for Shortest Paths Avoiding Convex Polygonal Obstacles", Technical Report A 86/02, FB 10, University of Saarbriicken, West Germany, 1986.

[21]

M. Sharir and A. Schorr, "On Shortest Paths in Polyhedral Spaces", SIAM Journal of Computing Vol. 15, No. 1, pp. 193-215, February 1986.

Digital Library

[22]

E. Welzl, "Constructing the Visibility Graph for n Line Segments in O(n2) Time", Information Processing Letters, Vol. 20 (1985), pp. 167-171.

Cited By

Farias RKallmann M(2020)Planar max flow maps and determination of lanes with clearanceAutonomous Robots10.1007/s10514-020-09917-wOnline publication date: 17-Jul-2020
https://doi.org/10.1007/s10514-020-09917-w
Boidot EMarzuoli AFeron E(2016)Optimal navigation policy for an autonomous agent operating in adversarial environments2016 IEEE International Conference on Robotics and Automation (ICRA)10.1109/ICRA.2016.7487483(3154-3160)Online publication date: May-2016
https://doi.org/10.1109/ICRA.2016.7487483
Elshawi RGudmundsson J(2012)Shortest Path in Transportation Network and Weighted SubdivisionsGraph Data Management10.4018/978-1-61350-053-8.ch020(463-474)Online publication date: 2012
https://doi.org/10.4018/978-1-61350-053-8.ch020
Show More Cited By

Index Terms

Path planning in 0/1/ weighted regions with applications

Recommendations

Shortest Path Queries Among Weighted Obstacles in the Rectilinear Plane

We study the problems of processing single-source and two-point shortest path queries among weighted polygonal obstacles in the rectilinear plane. For the single-source case, we construct a data structure in O ( n log ^3/2 n ) time and O ( n log n ) ...
Efficient algorithms for path planning and visibility problems
Path Refinement in Weighted Regions

In this paper, we study the weighted region problem (WRP) which is to compute a shortest path in a weighted partitioning of a plane. Recent results show that WRP is not solvable in any algebraic computation model over the rational numbers. Therefore, it ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SCG '88: Proceedings of the fourth annual symposium on Computational geometry

January 1988

403 pages

ISBN:0897912705

DOI:10.1145/73393

Chairman:
H. Edelsbrunner
Univ. of Illinois, Urbana-Champaign

Copyright © 1988 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]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 January 1988

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

CG88

Sponsor:

SIGACT

CG88: Symposium on Computational Geometery

June 6 - 8, 1988

Illinois, Urbana-Champaign, USA

Acceptance Rates

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
718
Total Downloads

Downloads (Last 12 months)97
Downloads (Last 6 weeks)21

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Farias RKallmann M(2020)Planar max flow maps and determination of lanes with clearanceAutonomous Robots10.1007/s10514-020-09917-wOnline publication date: 17-Jul-2020
https://doi.org/10.1007/s10514-020-09917-w
Boidot EMarzuoli AFeron E(2016)Optimal navigation policy for an autonomous agent operating in adversarial environments2016 IEEE International Conference on Robotics and Automation (ICRA)10.1109/ICRA.2016.7487483(3154-3160)Online publication date: May-2016
https://doi.org/10.1109/ICRA.2016.7487483
Elshawi RGudmundsson J(2012)Shortest Path in Transportation Network and Weighted SubdivisionsGraph Data Management10.4018/978-1-61350-053-8.ch020(463-474)Online publication date: 2012
https://doi.org/10.4018/978-1-61350-053-8.ch020
Bose PMaheshwari AShu CWuhrer S(2011)A survey of geodesic paths on 3D surfacesComputational Geometry: Theory and Applications10.1016/j.comgeo.2011.05.00644:9(486-498)Online publication date: 1-Nov-2011
https://dl.acm.org/doi/10.1016/j.comgeo.2011.05.006
Cook AWenk C(2011)Link distance and shortest path problems in the planeComputational Geometry: Theory and Applications10.1016/j.comgeo.2011.04.00444:8(442-455)Online publication date: 1-Oct-2011
https://dl.acm.org/doi/10.1016/j.comgeo.2011.04.004
Long JMould D(2009)Dendritic stylizationThe Visual Computer: International Journal of Computer Graphics10.1007/s00371-008-0217-025:3(241-253)Online publication date: 3-Feb-2009
https://dl.acm.org/doi/10.1007/s00371-008-0217-0
Cook AWenk C(2009)Link Distance and Shortest Path Problems in the PlaneProceedings of the 5th International Conference on Algorithmic Aspects in Information and Management10.1007/978-3-642-02158-9_13(140-151)Online publication date: 18-Jun-2009
https://dl.acm.org/doi/10.1007/978-3-642-02158-9_13
Daescu OPalmer J(2009)Modeling Optimal Beam Treatment with Weighted Regions for Bio-medical ApplicationsGeneralized Voronoi Diagram: A Geometry-Based Approach to Computational Intelligence10.1007/978-3-540-85126-4_9(215-232)Online publication date: 2009
https://doi.org/10.1007/978-3-540-85126-4_9
Stifter S(2005)Shortest non-synchronized motions parallel versions for shared memory crew modelsParallel Computation10.1007/3-540-57314-3_8(87-104)Online publication date: 29-May-2005
https://doi.org/10.1007/3-540-57314-3_8
Szczerba RChen DUhran J(1998)Planning Shortest Paths among 2D and 3D Weighted Regions Using Framed-SubspacesThe International Journal of Robotics Research10.1177/02783649980170050517:5(531-546)Online publication date: 1-May-1998
https://doi.org/10.1177/027836499801700505
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

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

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents