An optimal algorithm for rectangle placement

An optimal algorithm for rectangle placement

0.00 Avg rating0 Votes
Article ID: iaor20003523
Country: Netherlands
Volume: 24
Issue: 1/2
Start Page Number: 73
End Page Number: 80
Publication Date: Feb 1999
Journal: Operations Research Letters
Authors: , ,
Keywords: layout
Abstract:

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 property. This problem arises when we apply any one of a number of iterative improvement algorithms to the cutting stock problem or its variants. Chazelle has given an O(n)-time placement algorithm when the layout has the bottom-left property; we extend this result to the more general situation by presenting a O(n log n)-time algorithm.

Reviews

Required fields are marked *. Your email address will not be published.