Performance comparison of several data structures for storing VLSI geometry

This paper, in its first part, describes several well-known data structures for storing VLSI geometry and presents their implementation. KD tree data structure, as one of the first used for this purpose, is described in detail. Its usage is illustrated on the problem of design rule check (DRC) verification. Corner stitching, data structure introduced by Ousterhout, is presented and its main characteristics are given. Patented bucketing data structure is described. This data structure was independently implemented on the basis of patent description. The implementation was benchmark for other algorithms, as data structure that is used in modern CAD tools. Performance of the described algorithms was tested on several real-world layout examples in the second part of the paper. Speed of typical operations, together with memory requirements, was compared. In the conclusion, main advantages and disadvantages of the implemented algorithms are discussed.