On Minimum Width Packing of Rectilinear Blocks

Tetsuo ASANO

IEICE TRANSACTIONS (1976-1990)   Vol.E68    No.10    pp.647-649
Publication Date: 1985/10/25
Online ISSN: 
Print ISSN: 0000-0000
Type of Manuscript: LETTER
Category: Communication Theory

Full Text: PDF(265KB)>>
Buy this Article

We are given a set of rectilinear blocks without any overlap in the plane. We may move any block in the horizontal direction unless it intersects any other block. Then, the problem is to determine the minimum width of a rectangle which includes all of the blocks without any overlap and how much we should move each block in order to pack them into the rectangle. An O(n log n) time algorithm is presented, Where n is the total number of vertices of given blocks.