OPTIMAL-ALGORITHMS FOR RECTANGLE PROBLEMS ON A MESH-CONNECTED COMPUTER Academic Article uri icon

abstract

  • In this paper, 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, we 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 union of pairwise "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 planar 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 2n 2n MCC in O(n) time which is optimal. The algorithms compare favorably with the known sequential algorithms that have O(n log n) time complexity. 1988.

published proceedings

  • JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING

author list (cited authors)

  • LU, M., & VARMAN, P.

citation count

  • 11

complete list of authors

  • LU, M||VARMAN, P

publication date

  • April 1988