An O(n log n) Manhattan path algorithm

DOI10.1016/0020-0190(84)90105-4zbMATH Open0542.68052OpenAlexW2004369220MaRDI QIDQ795510FDOQ795510

Authors: Witold jun. Lipski 

Publication date: 1984

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

Full work available at URL: https://doi.org/10.1016/0020-0190(84)90105-4

Recommendations

• Finding a manhattan path and related problems
• A shortest-path algorithm for Manhattan graphs
• Finding Shortest Paths With Computational Geometry
• \(L_ 1\) shortest paths among polygonal obstacles in the plane
• Rectilinear shortest paths in the presence of rectangular barriers

zbMATH Keywords

computational geometryshortest pathsManhattan pathsegments on the plane

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Extremal problems in graph theory (05C35) Paths and cycles (05C38)

Cites Work

• Title not available (Why is that?)
• On the complexity of computing the measure of ∪[a _i ,b _i ]
• Finding a manhattan path and related problems
• Rectilinear line segment intersection, layered segment trees, and dynamization

Cited In (9)

• Approximation algorithms for decomposing octilinear polygons
• Functional pearl: nearest shelters in Manhattan
• A linear-time algorithm for a special case of disjoint set union
• A shortest-path algorithm for Manhattan graphs
• Finding a manhattan path and related problems
• Minimum convex partition of a polygon with holes by cuts in given directions
• Dynamic fractional cascading
• Finding Shortest Paths With Computational Geometry
• Rectilinear paths among rectilinear obstacles

This page was built for publication: An O(n log n) Manhattan path algorithm

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