[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.5555/3458064.3458115acmconferencesArticle/Chapter ViewAbstractPublication PagessodaConference Proceedingsconference-collections
research-article

Shortest paths among obstacles in the plane revisited

Published: 21 March 2021 Publication History

Abstract

Given a set of pairwise disjoint polygonal obstacles in the plane, finding an obstacle-avoiding Euclidean shortest path between two points is a classical problem in computational geometry and has been studied extensively. The previous best algorithm was given by Hershberger and Suri [FOCS 1993, SIAM J. Comput. 1999] and the algorithm runs in O(n log n) time and O(n log n) space, where n is the total number of vertices of all obstacles. The algorithm is time-optimal because Ω(n log n) is a lower bound. It has been an open problem for over two decades whether the space can be reduced to O(n). In this paper, we settle it by solving the problem in O(n log n) time and O(n) space, which is optimal in both time and space; we achieve this by modifying the algorithm of Hershberger and Suri. Like their original algorithm, our new algorithm can build a shortest path map for a source point s in O(n log n) time and O(n) space, such that given any query point t, the length of a shortest path from s to t can be computed in O(log n) time and a shortest path can be produced in additional time linear in the number of edges of the path.

References

[1]
B. Aronov. On the geodesic Voronoi diagram of point sites in a simple polygon. Algorithmica, 4:109--140, 1989.
[2]
D.Z. Chen, J. Hershberger, and H. Wang. Computing shortest paths amid convex pseudodisks. SIAM Journal on Computing, 42(3):1158--1184, 2013.
[3]
D.Z. Chen and H. Wang. A new algorithm for computing visibility graphs of polygonal obstacles in the plane. Journal of Computational Geometry, 6:316--345, 2015.
[4]
Y.-J. Chiang and J.S.B. Mitchell. Two-point Euclidean shortest path queries in the plane. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 215--224, 1999.
[5]
J. Driscoll, N. Sarnak, D. Sleator, and R.E. Tarjan. Making data structures persistent. Journal of Computer and System Sciences, 38(1):86--124, 1989.
[6]
H. Edelsbrunner, L. Guibas, and J. Stolfi. Optimal point location in a monotone subdivision. SIAM Journal on Computing, 15(2):317--340, 1986.
[7]
S.K. Ghosh and D.M. Mount. An output-sensitive algorithm for computing visibility graphs. SIAM Journal on Computing, 20(5):888--910, 1991.
[8]
L.J. Guibas and J. Hershberger. Optimal shortest path queries in a simple polygon. Journal of Computer and System Sciences, 39(2):126--152, 1989.
[9]
L.J. Guibas, J. Hershberger, D. Leven, M. Sharir, and R.E. Tarjan. Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons. Algorithmica, 2(1--4):209--233, 1987.
[10]
J. Hershberger. A new data structure for shortest path queries in a simple polygon. Information Processing Letters, 38(5):231--235, 1991.
[11]
J. Hershberger, V. Polishchuk, B. Speckmann, and T. Talvitie. Geometric kth shortest paths. In Proceedings of the 30th Annual Symposium on Computational Geometry (SoCG), pages 96:96--96:97, 2014. http://www.computational-geometry.org/SoCG-videos/socg14video/ksp/applet/index.html.
[12]
J. Hershberger and J. Snoeyink. Computing minimum length paths of a given homotopy class. Computational Geometry: Theory and Applications, 4(2):63--97, 1994.
[13]
J. Hershberger and S. Suri. An optimal algorithm for Euclidean shortest paths in the plane. SIAM Journal on Computing, 28(6):2215--2256, 1999.
[14]
J. Hershberger, S. Suri, and H. Yildiz. A near-optimal algorithm for shortest paths among curved obstacles in the plane. In Proceedings of the 29th Annual Symposium on Computational Geometry (SoCG), pages 359--368, 2013.
[15]
R. Inkulu, S. Kapoor, and S.N. Maheshwari. A near optimal algorithm for finding Euclidean shortest path in polygonal domain. In arXiv:1011.6481v1, 2010.
[16]
D. Kirkpatrick. Optimal search in planar subdivisions. SIAM Journal on Computing, 12(1):28--35, 1983.
[17]
D.T. Lee and F.P. Preparata. Euclidean shortest paths in the presence of rectilinear barriers. Networks, 14(3):393--410, 1984.
[18]
C.-H. Liu. A nearly optimal algorithm for the geodesic Voronoi diagram of points in a simple polygon. Algorithmica, 82:915--937, 2020.
[19]
J.S.B. Mitchell. A new algorithm for shortest paths among obstacles in the plane. Annals of Mathematics and Artificial Intelligence, 3(1):83--105, 1991.
[20]
J.S.B. Mitchell. Shortest paths among obstacles in the plane. International Journal of Computational Geometry and Applications, 6(3):309--332, 1996.
[21]
J.S.B. Mitchell, D.M. Mount, and C.H. Papadimitriou. The discrete geodesic problem. SIAM Journal on Computing, 16:647--668, 1987.
[22]
D.M. Mount. On finding shortest paths on convex polyhedra. Technical report, University of Maryland, College Park, MD 20742, 1985.
[23]
D.M. Mount. Storing the subdivision of a polyhedral surface. Discrete and Computational Geometry, 2:153--174, 1987.
[24]
E. Oh. Optimal algorithm for geodesic nearest-point Voronoi diagrams in simple polygons. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 391--409, 2019.
[25]
E. Oh and H.-K. Ahn. Voronoi diagrams for a moderate-sized point-set in a simple polygon. Discrete and Computational Geometry, 63:418--454, 2020.
[26]
E. Papadopoulou and D.T. Lee. A new approach for the geodesic Voronoi diagram of points in a simple polygon and other restricted polygonal domains. Algorithmica, 20:319--352, 1998.
[27]
H. Rohnert. Shortest paths in the plane with convex polygonal obstacles. Information Processing Letters, 23(2):71--76, 1986.
[28]
Y. Schreiber and M. Sharir. An optimal-time algorithm for shortest paths on a convex polytope in three dimensions. Discrete and Computational Geometry, 39:500--579, 2008.
[29]
M.I. Shamos and D. Hoey. Closest-point problems. In Proceedings of the 16th Annual Symposium on Foundations of Computer Science (FOCS), pages 151--162, 1975.
[30]
M. Sharir and A. Schorr. On shortest paths in polyhedral spaces. SIAM Journal on Computing, 15(1):193--215, 1986.
[31]
J.A. Storer and J.H. Reif. Shortest paths in the plane with polygonal obstacles. Journal of the ACM, 41(5):982--1012, 1994.

Cited By

View all
  • (2021)A new algorithm for Euclidean shortest paths in the planeProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3406325.3451037(975-988)Online publication date: 15-Jun-2021

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
SODA '21: Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms
January 2021
3063 pages
ISBN:9781611976465
  • Program Chair:
  • Dániel Marx

Sponsors

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 21 March 2021

Check for updates

Qualifiers

  • Research-article

Conference

SODA '21
Sponsor:
SODA '21: ACM-SIAM Symposium on Discrete Algorithms
January 10 - 13, 2021
Virginia, Virtual Event

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)3
  • Downloads (Last 6 weeks)0
Reflects downloads up to 13 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2021)A new algorithm for Euclidean shortest paths in the planeProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3406325.3451037(975-988)Online publication date: 15-Jun-2021

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media