Finding a manhattan path and related problems

DOI10.1002/NET.3230130308MaRDI QIDQ3313268zbMATH OpenOpenAlexFDO

Authors Witold jun. Lipski

Publication date 1983

Published in Networks (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/2142/74073

zbMATH Keywords

crossingsintersections of segmentsManhattan pathnonintersecting segments

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• An O(n log n) Manhattan path algorithm
• Rectilinear shortest paths in the presence of rectangular barriers
• Approximating a minimum Manhattan network
• Euclidean shortest paths in the presence of rectilinear barriers
• A shortest-path algorithm for Manhattan graphs

Cites work

• Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems
• Erratum
• scientific article; zbMATH DE number 3690676 (Why is no real title available?)

Cited in

(14)

• Minimum dissection of a rectilinear polygon with arbitrary holes into rectangles
• 3D rectangulations and geometric matrix multiplication
• Extracting compact fuzzy rules based on adaptive data approximation using B-splines
• Approximation algorithms for decomposing octilinear polygons
• Rectilinear paths among rectilinear obstacles
• scientific article; zbMATH DE number 1629849 (Why is no real title available?)
• 3D rectangulations and geometric matrix multiplication
• Minimum k-adjacent rectangles of orthogonal polygons and its application
• Polygon Area Decomposition for Multiple-Robot Workspace Division
• Between Broadway and the Hudson: A Bijection of Corridor Paths
• Minimum convex partition of a polygon with holes by cuts in given directions
• An O(n log n) Manhattan path algorithm
• Rectangular partition is polynomial in two dimensions but NP-complete in three
• Dynamic fractional cascading

This page was built for publication: Finding a manhattan path and related problems

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