An O(n log n) algorithm for 1-D tile compaction

A simple O(n log n) algorithm is presented for performing one-dimensional tile compaction on a planar constraint network. The algorithm works only on planar constraints networks: those resulting from considering all components to be on single layer. The top and bottom zones in this example attain their minimum widths of 15 only by forcing the other zone to have width 25, while the best configuration has width 20 which is the minimum width of the middle zone. VLSI circuits often result in nonplanar constraint networks, even though interconnect parallel to the direction of compaction is not part of the constraint network. The algorithm could be used to obtain an initial guess at the width, possibly saving several iterations of the more expensive minimum-cost flow method.<>