[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/28395.28402acmconferencesArticle/Chapter ViewAbstractPublication PagesstocConference Proceedingsconference-collections
Article
Free access

Approximation algorithms for shortest path motion planning

Published: 01 January 1987 Publication History

Abstract

This paper gives approximation algorithms of solving the following motion planning problem: Given a set of polyhedral obstacles and points s and t, find a shortest path from s to t that avoids the obstacles. The paths found by the algorithms are piecewise linear, and the length of a path is the sum of the lengths of the line segments making up the path. Approximation algorithms will be given for versions of this problem in the plane and in three-dimensional space. The algorithms return an ε-short path, that is, a path with length within (1 + ε) of shortest. Let n be the total number of faces of the polyhedral obstacles, and ε a given value satisfying Ο < ε ≤ π. The algorithm for the planar case requires Ο(n log n)/ε time to build a data structure of size Ο(n/ε). Given points s and t, and ε-short path from s to t can be found with the use of the data structure in time Ο(n/ε + n log n). The data structure is associated with a new variety of Voronoi diagram. Given obstacles SΕ3 and points s, t ε E3, an ε-short path between s and t can be found in Ο(n2λ(n) log(n/ε)/ε4 + n2 lognp log(n logp)) time, where p is the ratio of the length of the longest obstacle edge to the distance between s to t. The function λ(n) = α(n)Ο(α(n)Ο(1)), where the α(n) is a form of inverse of Ackermann's function. For log(1/ε) and log p that are Ο(log n), this bound is Ο(log n2(n)λ(n)/ε4).

References

[1]
Takao Asano, Tetsuo Asano, L. Guibas, J~ Hershberger, and H. Imai. Visibilitypolygon search and Euclidean shortest paths. In Proc. 26th IEEE FOC$, pages 1.55-164, } 985.
[2]
P. Chew. There is a planar graph almost as good as the complete graph. In Proc. 2nd Syrup. on Comp. Geometry, pages 169-177, 1986.
[3]
H.G. Eggleston. Convexity. Cambridge University Press, Cambridge, 1958.
[4]
M. Fredman and R. E. Tarjan. Fibonacci heaps and their uses in improved network optimization problems. Ill Proc. 25th IEEE FOCS, pages 338-346, 1984.
[5]
D. Mount. On finding shortest paths on convex polyhedra. Technical Report, Department of Computer Science, Univ. of Maryland, 1984.
[6]
C.H. Papadimitriou. An algorithm for shortest-path motion in three dimensions. Information Processing Letters, 20:259- 263, 1985.
[7]
J. Rcif and J. A. Storcr. Shortest paths in Euclidean space with polyhedral obstacles. Technical Report CS-85-121, Departincnt of Computer Science, Brandeis Univ., 1985.
[8]
M. Sharir and A. Baltsan. On shortest paths amidst convex polyhedra. In Proc. 2nd Symp. on Comp. Geometry, pages 193-206, } 986.
[9]
M. Sharir, R. Cole, K. Kedem, D. Leven, R. Pollack, and S. S ifrony. Geometric applications of Davenport-Schinzel sequences. In Proc. 27th IEEE FOCS, pages 77-86, } 986.
[10]
M. Sharir and A. Schorr. On shortest paths in polyhedral spaces. In Proc. 16th Annual SIGACT Syrup., pages 144-153, 1984.
[11]
A.C. Yao. On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM Journal on Computing, } 1:721-736, 1982.
[12]
C.K. Yap. Algorithmic motion planning. In j. T. Schwartz and C. K. Yap, editors, Advance in Robotics, Volume I, Lawrence Erlbaum Associates, 1985.

Cited By

View all

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
STOC '87: Proceedings of the nineteenth annual ACM symposium on Theory of computing
January 1987
471 pages
ISBN:0897912217
DOI:10.1145/28395
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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 1987

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Article

Conference

STOC87
Sponsor:

Acceptance Rates

STOC '87 Paper Acceptance Rate 50 of 165 submissions, 30%;
Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25
57th Annual ACM Symposium on Theory of Computing (STOC 2025)
June 23 - 27, 2025
Prague , Czech Republic

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)153
  • Downloads (Last 6 weeks)8
Reflects downloads up to 09 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Online Euclidean SpannersACM Transactions on Algorithms10.1145/368179021:1(1-22)Online publication date: 4-Nov-2024
  • (2024)Towards Instance-Optimal Euclidean Spanners2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00099(1579-1609)Online publication date: 27-Oct-2024
  • (2024)Generalized Sweeping Line SpannersTheoretical Computer Science10.1016/j.tcs.2024.114390(114390)Online publication date: Jan-2024
  • (2024)Minimum weight Euclidean ( 1 + ɛ )-spannersEuropean Journal of Combinatorics10.1016/j.ejc.2024.103927118:COnline publication date: 1-May-2024
  • (2024)Routing on heavy path WSPD spannersComputational Geometry10.1016/j.comgeo.2024.102121123(102121)Online publication date: Dec-2024
  • (2023)A Simple and Efficient Method for Accelerating Construction of the Gap-Greedy SpannerInternational Journal of Foundations of Computer Science10.1142/S012905412350011935:04(453-481)Online publication date: 9-Jun-2023
  • (2023)Sub-quadratic (1+ϵ)-approximate Euclidean Spanners, with Applications2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00014(98-112)Online publication date: 6-Nov-2023
  • (2023)Optimal Fault-Tolerant Spanners in Euclidean and Doubling Metrics: Breaking the Ω (log n) Lightness Barrier2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00013(77-97)Online publication date: 6-Nov-2023
  • (2023)On path-greedy geometric spannersComputational Geometry: Theory and Applications10.1016/j.comgeo.2022.101948110:COnline publication date: 1-Mar-2023
  • (2023)On the Spanning and Routing Ratio of the Directed Theta-Four GraphDiscrete & Computational Geometry10.1007/s00454-023-00597-8Online publication date: 6-Oct-2023
  • Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media