John K. Ousterhout

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-83-114

, 1983

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1983/CSD-83-114.pdf

Corner stitching is a technique for representing rectangular two-dimensional objects. It appears to be especially well-suited for interactive editing systems for VLSI layouts. The data structure has two important features: first, empty space is represented explicitly; and second, rectangular areas are stitched together at their corners like a patchwork quilt. This organization results in fast algorithms (linear time or better) for searching, creation, deletion, stretching, and compaction. The algorithms are presented under a simplified model of VLSI circuits, and the storage requirements of the structure are discussed. Measurements indicate that corner stitching requires approximately three times as much memory space as the simplest possible representation.


BibTeX citation:

@techreport{Ousterhout:CSD-83-114,
    Author= {Ousterhout, John K.},
    Title= {Corner Stitching: a Data Structuring Technique for VLSI Layout Tools},
    Year= {1983},
    Month= {Dec},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1983/6352.html},
    Number= {UCB/CSD-83-114},
    Abstract= {Corner stitching is a technique for representing rectangular two-dimensional objects.  It appears to be especially well-suited for interactive editing systems for VLSI layouts. The data structure has two important features: first, empty space is represented explicitly; and second, rectangular areas are stitched together at their corners like a patchwork quilt. This organization results in fast algorithms (linear time or better) for searching, creation, deletion, stretching, and compaction. The algorithms are presented under a simplified model of VLSI circuits, and the storage requirements of the structure are discussed. Measurements indicate that corner stitching requires approximately three times as much memory space as the simplest possible representation.},
}

EndNote citation:

%0 Report
%A Ousterhout, John K. 
%T Corner Stitching: a Data Structuring Technique for VLSI Layout Tools
%I EECS Department, University of California, Berkeley
%D 1983
%@ UCB/CSD-83-114
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1983/6352.html
%F Ousterhout:CSD-83-114