Optimal algorithm for rectangle placement

Patrick Healy; Marcus Creavin; Ago Kuusik

doi:10.1016/S0167-6377(98)00048-0

Optimal algorithm for rectangle placement

Patrick Healy, Marcus Creavin, Ago Kuusik

University of Limerick

Research output: Contribution to journal › Article › peer-review

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; this result is extended to a more general situation.

Original language	English
Pages (from-to)	73-80
Number of pages	8
Journal	Operations Research Letters
Volume	24
Issue number	1
DOIs	https://doi.org/10.1016/S0167-6377(98)00048-0
Publication status	Published - Feb 1999

Access to Document

10.1016/S0167-6377(98)00048-0

Cite this

@article{51826b0710634222afd5e66023a15ed0,

title = "Optimal algorithm for rectangle placement",

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; this result is extended to a more general situation.",

author = "Patrick Healy and Marcus Creavin and Ago Kuusik",

year = "1999",

month = feb,

doi = "10.1016/S0167-6377(98)00048-0",

language = "English",

volume = "24",

pages = "73--80",

journal = "Operations Research Letters",

issn = "0167-6377",

number = "1",

}

TY - JOUR

T1 - Optimal algorithm for rectangle placement

AU - Healy, Patrick

AU - Creavin, Marcus

AU - Kuusik, Ago

PY - 1999/2

Y1 - 1999/2

N2 - 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; this result is extended to a more general situation.

AB - 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; this result is extended to a more general situation.

UR - https://www.scopus.com/pages/publications/0032673001

U2 - 10.1016/S0167-6377(98)00048-0

DO - 10.1016/S0167-6377(98)00048-0

M3 - Article

AN - SCOPUS:0032673001

SN - 0167-6377

VL - 24

SP - 73

EP - 80

JO - Operations Research Letters

JF - Operations Research Letters

IS - 1

ER -

Optimal algorithm for rectangle placement

Abstract

Access to Document

Other files and links

Fingerprint

Cite this