Parallel rectilinear shortest paths with rectangular obstacles
Mikhail J. Atallah, D. Chen · 1990
Let P be a simple rectilinear convex polygon of size O(n) inside which lie n pairwise disjoint rectangular rectilinear obstacles.We provide parallel techniques for computing rectilinear shortest paths that avoid the set of obstacles in P. Specifically, we compute descriptions of shortest paths in O(log' n) time, with O(n'/ log' n) processors in the CREW-PRAM model if source and destination are on the boundary of P, with O(n'/ log n) processors if the source is an obsta-