ABSTRACT
Several innovative data structures have been developed for floorplanning. The computational geometry literature describes a number of geometric data structures. Implementing geometric data structures can be time consuming, but they may be found in algorithmic or geometric libraries. The mathematical structure that comes closest to representing a circuit is the hypergraph. Most physical designs can be represented as a set of axis-parallel rectangles. The boundaries of these rectangles can be viewed as intervals. Max-plus lists are applicable to slicing floorplans, technology mapping, and buffer insertion problems. A layout data structure stores and manipulates the rectangles on each layer. The corner-stitching data structure was proposed by Ousterhout to store nonoverlapping rectilinear circuit components in MAGIC. The space requirements of corner stitching must take into account the number of vacant tiles. The underlying principle of the quad tree is to recursively subdivide the two-dimensional layout area into four quads until a stopping criterion is satisfied.
