Shortest path between two simple polygons

DOI10.1016/0020-0190(87)90150-5MaRDI QIDQ1107993zbMATHOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(10)

• Algorithms and Computation
• Computing simple paths from given points inside a polygon
• scientific article; zbMATH DE number 1796964 (Why is no real title available?)
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• An algorithmic approach to some problems in terrain navigation
• Finding a shortest Hamiltonian path inside a simple polygon
• Finding simple paths on given points in a polygonal region
• Shortest paths in simple polygons with polygon-meet constraints
• Routing in polygonal domains
• The shortest path in a simple polygon with obstacles

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)