SOLVING COMPUTATIONAL GEOMETRY PROBLEMS ON MESH-CONNECTED COMPUTERS

Parallel algorithms to solve several computational geometric problems on mesh-connected computers (MCC's) and systolic arrays are designed and analyzed. We present parallel MCC algorithms to solve the following proximity problems. Given a set of n planar points represented by their Cartesian coordinates, determine the nearest neighbor for each point and find the closest pair of the set. Our algorithms execute on a {dollar}sqrt{lcub}n{rcub}timessqrt{lcub}n{rcub}{dollar} MCC with constant storage per processor and the time performance is {dollar}O(sqrt{lcub}n{rcub}){dollar} which is optimal. We also describe parallel algorithm to construct the Voronoi diagram and the minimum spanning tree of a given set of n planar points, and to find the closest pair between two sets on a {dollar}sqrt{lcub}n{rcub}timessqrt{lcub}n{rcub}{dollar} MCC in {dollar}O(sqrt{lcub}n{rcub}{lcub}rm log{rcub}n){dollar} time. The best known sequential algorithms for these problems have an optimal {dollar}O(n{lcub}rm log{rcub}n){dollar} time complexity.; In addition, MCC algorithms for computing several properties of a set of, possibly intersecting rectangles are presented. Given a set of n iso-oriented rectangles, we describe MCC algorithms for determining the area of the logic "OR" of these rectangles, the area of pairwise logic "AND" of the rectangles, the largest number of rectangles that overlap and the minimum separation between any pair of a set of non-overlapping rectangles. All these algorithms can be implemented on a {dollar}sqrt{lcub}n{rcub}timessqrt{lcub}n{rcub}{dollar} MCC in an optimal {dollar}O(sqrt{lcub}n{rcub}){dollar} time, and compare favorably with the known sequential algorithms which have {dollar}O(n{lcub}rm log{rcub}n){dollar} time complexity.; For the above tasks, we also describe methods to solve problems of size n on MCC's with p processors, where {dollar}p < n{dollar}. Lower bounds on the time complexity are demonstrated and the optimal size of MCC's to be used is derived.; Finally, we present systolic algorithms to solve the segment intersection counting problem and to construct the convex hull of a set of planar points, as well as an update algorithm for the fixed size circle placement problem. For a problem of size n, our algorithms use a systolic array of {dollar}nsp{lcub}2/3{rcub}times nsp{lcub}2/3{rcub}{dollar} cells and have a time complexity of {dollar}O(nsp{lcub}2/3{rcub}){dollar}.