John K. Ousterhout

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-83-114
December 1982

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},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1982},
    Month = {Dec},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1982/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 1982
%@ UCB/CSD-83-114
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1982/6352.html
%F Ousterhout:CSD-83-114