Packing squares into a square

Joseph Y.T. Leung; Tommy W. Tam; C. S. Wong; Gilbert H. Young; Francis Y.L. Chin

doi:10.1016/0743-7315(90)90019-L

Packing squares into a square

Joseph Y.T. Leung
, Tommy W. Tam
, C. S. Wong
, Gilbert H. Young
, Francis Y.L. Chin

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

149 Scopus citations

Abstract

The problem of determining whether a set of rectangles can be orthogonally packed into a larger rectangle has been studied as a geometric packing problem and as a floor planning problem. Recently, there is some renewed interest in this problem, as it is related to a job scheduling problem in a partitionable mesh connected system. In this paper we show that the problem of deciding whether a set of squares can be packed into a larger square is strongly NP-complete, answering an open question posed by Li and Cheng.

Original language	English (US)
Pages (from-to)	271-275
Number of pages	5
Journal	Journal of Parallel and Distributed Computing
Volume	10
Issue number	3
DOIs	https://doi.org/10.1016/0743-7315(90)90019-L
State	Published - Nov 1990
Externally published	Yes

All Science Journal Classification (ASJC) codes

Software
Theoretical Computer Science
Hardware and Architecture
Computer Networks and Communications
Artificial Intelligence

Access to Document

10.1016/0743-7315(90)90019-L

Cite this

@article{d1f05283f95545d4a434f6372fcf3fe4,

title = "Packing squares into a square",

abstract = "The problem of determining whether a set of rectangles can be orthogonally packed into a larger rectangle has been studied as a geometric packing problem and as a floor planning problem. Recently, there is some renewed interest in this problem, as it is related to a job scheduling problem in a partitionable mesh connected system. In this paper we show that the problem of deciding whether a set of squares can be packed into a larger square is strongly NP-complete, answering an open question posed by Li and Cheng.",

author = "Leung, \{Joseph Y.T.\} and Tam, \{Tommy W.\} and Wong, \{C. S.\} and Young, \{Gilbert H.\} and Chin, \{Francis Y.L.\}",

note = "Funding Information: * Research supported in part by the ONR Grant N00014-87-K-0833 in part by a grant from Texas Instruments, Inc.",

year = "1990",

month = nov,

doi = "10.1016/0743-7315(90)90019-L",

language = "English (US)",

volume = "10",

pages = "271--275",

journal = "Journal of Parallel and Distributed Computing",

issn = "0743-7315",

publisher = "Academic Press Inc.",

number = "3",

}

TY - JOUR

T1 - Packing squares into a square

AU - Leung, Joseph Y.T.

AU - Tam, Tommy W.

AU - Wong, C. S.

AU - Young, Gilbert H.

AU - Chin, Francis Y.L.

N1 - Funding Information: * Research supported in part by the ONR Grant N00014-87-K-0833 in part by a grant from Texas Instruments, Inc.

PY - 1990/11

Y1 - 1990/11

N2 - The problem of determining whether a set of rectangles can be orthogonally packed into a larger rectangle has been studied as a geometric packing problem and as a floor planning problem. Recently, there is some renewed interest in this problem, as it is related to a job scheduling problem in a partitionable mesh connected system. In this paper we show that the problem of deciding whether a set of squares can be packed into a larger square is strongly NP-complete, answering an open question posed by Li and Cheng.

AB - The problem of determining whether a set of rectangles can be orthogonally packed into a larger rectangle has been studied as a geometric packing problem and as a floor planning problem. Recently, there is some renewed interest in this problem, as it is related to a job scheduling problem in a partitionable mesh connected system. In this paper we show that the problem of deciding whether a set of squares can be packed into a larger square is strongly NP-complete, answering an open question posed by Li and Cheng.

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

UR - https://www.scopus.com/pages/publications/0025521123#tab=citedBy

U2 - 10.1016/0743-7315(90)90019-L

DO - 10.1016/0743-7315(90)90019-L

M3 - Article

AN - SCOPUS:0025521123

SN - 0743-7315

VL - 10

SP - 271

EP - 275

JO - Journal of Parallel and Distributed Computing

JF - Journal of Parallel and Distributed Computing

IS - 3

ER -

Packing squares into a square

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this