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

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 01, 1987
Accession Number
ADA182201

Entities

People

  • Charles E. Leiserson
  • Cynthia A. Phillips

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Algorithms
  • Alphabets
  • Availability
  • Boundaries
  • Classification
  • Computer Science
  • Computers
  • Databases
  • Geometry
  • Identification
  • Information Processing
  • Information Systems
  • Lists (Data Structures)
  • Massachusetts
  • Security
  • Trees (Data Structures)
  • Very Large Scale Integration

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Electromagnetic Wave Scattering and Antenna Radiation Engineering
  • Graph Algorithms and Convex Optimization.

Technology Areas

  • Space
  • Space - Space Objects