A Space-efficient Algorithm for Finding the Connected Components of Rectangles in the Plane
Author(s)
Leiserson, Charles E.; Phillips, Cynthia A.
DownloadMIT-LCS-TM-323.pdf (4.520Mb)
Metadata
Show full item recordAbstract
We present an algorithm 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 lg N) time and requires no more than O(N) transfers between primary and secondary memory.
Date issued
1987-02Series/Report no.
MIT-LCS-TM-323