OPTIMAL PARALLEL ALGORITHMS FOR RECTILINEAR LINK-DISTANCE PROBLEMS

We provide optimal parallel solutions to several link-distance problem s set in trapezoided rectilinear polygons. All our main parallel algor ithms are deterministic acid designed to run on the exclusive read exc lusive write parallel random access machine (EREW PRAM). Let P be a tr apezoided rectilinear simple polygon with n vertices. In O(log n) time using O(n/log n) processors we can optimally compute: 1. Minimum rect ilinear link paths, or shortest paths in the L(1) metric from any poin t in P to all vertices of P. 2. Minimum rectilinear link paths from an y segment inside P to all vertices of P. 3. The rectilinear window (hi stogram) partition of P. 4. Both covering radii and vertex intervals f or any diagonal of P. 5. A data structure to support rectilinear link- distance queries between any two points in P (queries can be answered optimally in O(log n) time by uniprocessor). Our solution to 5 is base d on a new linear-time sequential algorithm for this problem which is also provided here. This improves on the previously best-known sequent ial algorithm for this problem which used O(n log n) time and space.(5 ) We develop techniques for solving link-distance problems in parallel which are expected to find applications in the design of other parall el computational geometry algorithms. We employ these parallel techniq ues, for example, to compute (on a CREW PRAM) optimally the link diame ter, the link center, and the central diagonal of a rectilinear polygo n.