Shortest path between two simple polygons

DOI10.1016/0020-0190(87)90150-5zbMATH Open0653.68025OpenAlexW2005422822MaRDI QIDQ1107993FDOQ1107993

Authors: T. Asano, Tetsuo Asano, Hideki Imai 

Publication date: 1987

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(87)90150-5

Recommendations

• Time and space efficient algorithms for shortest paths between convex polygons
• Shortest paths in the plane with convex polygonal obstacles
• Shortest paths in the plane with polygonal obstacles
• A nearly optimal algorithm for finding \(L _{1}\) shortest paths among polygonal obstacles in the plane
• Visibility of disjoint polygons

zbMATH Keywords

computational complexitycomputational geometryshortest pathvisibility polygonwire routing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Other problems of combinatorial convexity (52A37)

Cites Work

• A note on two problems in connexion with graphs
• Euclidean shortest paths in the presence of rectilinear barriers
• Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time
• Visibility of disjoint polygons

Cited In (7)

• An algorithmic approach to some problems in terrain navigation
• Algorithms and Computation
• Shortest paths in simple polygons with polygon-meet constraints
• The shortest path in a simple polygon with obstacles
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Finding a shortest Hamiltonian path inside a simple polygon
• Title not available (Why is that?)

This page was built for publication: Shortest path between two simple polygons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1107993)