An optimal algorithm for rectangle placement

In this paper we consider the problem of placing efficiently a rectangle in a two-dimensional layout that may not have the bottom-left placement prope rty. This problem arises when we apply any one of a number of iterative imp rovement algorithms to the cutting stock problem or its variants. Chazelle has given an O(n)-time placement algorithm when the layout has the bottom-l eft property; we extend this result to the more general situation by presen ting a Theta(n log n)-time algorithm (C) 1999 Published by Elsevier Science B.V. All rights reserved.