An Ω(k/sup 2/) lower bound for area optimization of spiral floorplans
Cheng-Hsi Chen, Ioannis G. Tollis · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · 1996
Let F be a spiral floorplan where each of its five basic rectangles has k implementations. In this paper, we show that there can be as many as /spl Omega/(k/sup 2/) useful implementations generated for F, in the worst case. This implies that the previously known O(k/sup 2/ log k)-time algorithm is almost optimal.