Optimal algorithms for rectangle problems on a meshconnected computer
Academic Article

 Overview

 Identity

 Additional Document Info

 View All

Overview
abstract

In this paper, MeshConnected Computer (MCC) algorithms for computing several properties of a set of, possibly intersecting rectangles are presented. Given a set of n isooriented 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 fixedsize 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 2√n × 2√n 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.
author list (cited authors)
citation count
publication date
publisher
published in
Identity
Digital Object Identifier (DOI)
Additional Document Info
start page
end page
volume
issue