A framework for 1-D compaction with forbidden region avoidance [VLSI layout]

In this paper the authors consider the one-dimensional compaction problem when the layout area contains forbidden regions and the layout components are allowed to move across these regions. Assuming a feasible layout is given containing k forbidden regions and n layout components where the i-th layout component is a rectilinear polygon consisting of υ_i vertical edges, υ=Σ_i=1ⁿ υ_i, the authors present an algorithm that determines the positions of the layout components resulting in minimum area in O(σlogσ+σn logn) time with an additional O((υ+k)logk+(υ+σ)logυ_max) preprocessing time, where υ_max=max_1⩽i⩽n υ_i. The quantity σ measures the interaction between the layout components and the forbidden regions, σ⩽υk. The authors also describe variants of this algorithm that makes the running time more problem-dependent. Their algorithms make use of an elegant characterisation of a layout of minimum area