On parallel rectilinear obstacle-avoiding paths

DOI10.1016/0925-7721(93)90004-PzbMath0801.68156MaRDI QIDQ1314529

Danny Z. Chen, Mikhail J. Atallah

Publication date: 29 November 1994

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0925-7721(93)90004-p

zbMATH Keywords

convex polygon; partitioning scheme; CREW PRAM; query processing; recursion tree; space complexity; data structure; processor complexity; obstacle-avoiding paths

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

68W15: Distributed algorithms

Related Items

ON GEOMETRIC PATH QUERY PROBLEMS, ON CONNECTING RED AND BLUE RECTILINEAR POLYGONAL OBSTACLES WITH NONINTERSECTING MONOTONE RECTILINEAR PATHS, Planar rectilinear shortest path computation using corridors, Rectilinear short path queries among rectangular obstacles, Computing an \(L_1\) shortest path among splinegonal obstacles in the plane

Cites Work

• Unnamed Item
• On the X-Y convex hull of a set of X-Y polygons
• Rectilinear shortest paths in the presence of rectangular barriers
• Parallel rectilinear shortest paths with rectangular obstacles
• Efficient Parallel Algorithms for String Editing and Related Problems
• Parallel Merge Sort
• Cascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms
• ORTHOGONAL SHORTEST ROUTE QUERIES AMONG AXES PARALLEL RECTANGULAR OBSTACLES
• The Parallel Evaluation of General Arithmetic Expressions