MESH-CONNECTED COMPUTER ALGORITHMS FOR RECTANGLE-INTERSECTION PROBLEMS.

Mesh-connected computer (MCC) algorithms for computing several properties of a set of possibly intersecting rectangles are presented. Given a set of n iso-oriented rectangles, the authors describe MCC algorithms for determining the following properties: (i) the area of the logic OR of these rectangles (i. e. the area of the region covered by at least one rectangle); (ii) the area of the logic AND of the rectangles (i. e. , the area of the region covered by two or more rectangles); (iii) the largest number of rectangles that overlap; this solves the fixed-size rectangle placement problem, i. e. given a set of plan points and a rectangle, find a placement of the rectangle in the plane so that the number of points covered by the rectangle is maximal; (iv) the minimum separation between any pair of a set of nonoverlapping rectangles. All these algorithms can be implemented on a ROOT n multiplied by ROOT n MCC in O( ROOT n) time. The best known algorithms for the above problems are sequential and have optimal O(n log n) time complexity.

MESH-CONNECTED COMPUTER ALGORITHMS FOR RECTANGLE-INTERSECTION PROBLEMS. Conference Paper