An O(n log n) Manhattan path algorithm

DOI10.1016/0020-0190(84)90105-4zbMath0542.68052OpenAlexW2004369220MaRDI QIDQ795510

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

zbMATH Keywords

shortest pathscomputational geometryManhattan pathsegments on the plane

Mathematics Subject Classification ID

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

Related Items (4)

Approximation algorithms for decomposing octilinear polygons ⋮ Dynamic fractional cascading ⋮ Rectilinear paths among rectilinear obstacles ⋮ A linear-time algorithm for a special case of disjoint set union

Cites Work

• Unnamed Item
• Finding a manhattan path and related problems
• Rectilinear line segment intersection, layered segment trees, and dynamization
• On the complexity of computing the measure of ∪[a _i ,b _i ]

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