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 journalArticlepeer-review

127 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 languageEnglish (US)
Pages (from-to)271-275
Number of pages5
JournalJournal of Parallel and Distributed Computing
Volume10
Issue number3
DOIs
StatePublished - Nov 1990
Externally publishedYes

All Science Journal Classification (ASJC) codes

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

Fingerprint

Dive into the research topics of 'Packing squares into a square'. Together they form a unique fingerprint.

Cite this