MESH-CONNECTED COMPUTER ALGORITHMS FOR RECTANGLE-INTERSECTION PROBLEMS.
- Additional Document Info
- View All
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.
Proceedings of the International Conference on Parallel Processing
author list (cited authors)
complete list of authors