Wall-stitching:A New Data Structuring Technique for Layout Tools of IC Design

In this paper, a new data structuring technique called wall-stitching is described, which represents the rectangular dissections on a plane and finds app lications in layout tools for IC design. Upon the wall-stitching data structure,each tile on a rectangular dissection is assigned with a set of neighboring pointers and sti tched together. Wall-stitching technique supports fast geometry operations like point location, neighbor finding, path search, etc.. More importantly, it can describe both the geometrical and topological details on a rectangular dissection, and there fore, it can be used as a unified data structure in an integrated IC layout system.