A framework for 1-D compaction with forbidden region avoidance Academic Article uri icon


  • In this paper we consider the 1-dimensional compaction problem when the layout area contains forbidden regions and the layout components are allowed to move across these regions. Assume we are given a feasible layout containing k forbidden regions of rectangular shape and n layout components, each being a rectilinear polygon consisting of υi vertical edges withυ=∑;i=1nυi. We present an algorithm that determines the positions of the layout components resulting in minimum area in O(σ log σ + σn log n) time with an O((υ + k)log k + (υ + σ)log υ) preprocessing time. The quantity σ measures the interaction between the layout components and the forbidden regions, σ⩽υk. We also describe variants of this algorithm that make the running time more problem-dependent and consider forbidden regions of special structure. Our algorithms make use of an elegant characterization of a layout of minimum area.

publication date

  • January 1, 1992