Accession Number : ADA182201

Title :   A Space-Efficient Algorithm for Finding the Connected Components of Rectangles in the Plane.

Descriptive Note : Technical rept.,

Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE

Personal Author(s) : Leiserson,Charles E ; Phillips,Cynthia A

PDF Url : ADA182201

Report Date : Feb 1987

Pagination or Media Count : 22

Abstract : An algorithm is presented for determining the connectivity of a set of N rectangles in the plane, a problem central to avoiding aliasing in VLSI design rule checkers. Previous algorithms for this problem either worked slowly with a small amount of primary memory space, or worked quickly but used more space. Our algorithm uses O(W) primary memory space, where W, the scan width, is the maximum number of rectangles to cross any vertical cut. The algorithm runs in O(N 1g N) time and requires no more than O(N) transfers between primary and secondary memory. Keywords: Very large scale integration; Computational geometry; Design rule checking; Algorithms; Rectangles; Connected components; Scanning.

Descriptors :   *ALGORITHMS, COMPUTATIONS, CUTTING, GEOMETRY, INTEGRATION, MEMORY DEVICES, SECONDARY, SCANNING

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE