19950901
Optimal parallel algorithms for rectilinear linkdistance problems
Publication
Publication
Algorithmica , Volume 14  Issue 3 p. 261 289
We provide optimal parallel solutions to several linkdistance problems set in trapezoided rectilinear polygons. All our main parallel algorithms are deterministic and designed to run on the exclusive read exclusive write parallel random access machine (EREW PRAM). Let P be a trapezoided rectilinear simple polygon with n vertices. In O(log n) time using O(n/log n) processors we can optimally compute: 1. Minimum réctilinear link paths, or shortest paths in the L1 metric from any point in P to all vertices of P. 2. Minimum rectilinear link paths from any segment inside P to all vertices of P. 3. The rectilinear window (histogram) partition of P. 4. Both covering radii and vertex intervals for any diagonal of P. 5. A data structure to support rectilinear linkdistance queries between any two points in P (queries can be answered optimally in O(log n) time by uniprocessor). Our solution to 5 is based on a new lineartime sequential algorithm for this problem which is also provided here. This improves on the previously bestknown sequential algorithm for this problem which used O(n log n) time and space.5 We develop techniques for solving linkdistance problems in parallel which are expected to find applications in the design of other parallel computational geometry algorithms. We employ these parallel techniques, for example, to compute (on a CREW PRAM) optimally the link diameter, the link center, and the central diagonal of a rectilinear polygon.
Additional Metadata  

Algorithms and data structures, Computational geometry, Link distance, Parallel computation, Rectilinear polygons  
dx.doi.org/10.1007/BF01206332  
Algorithmica  
Organisation  School of Computer Science 
Lingas, A. (A.), Maheshwari, A, & Sack, J.R. (1995). Optimal parallel algorithms for rectilinear linkdistance problems. Algorithmica, 14(3), 261–289. doi:10.1007/BF01206332
