On Minimum Width Packing of Rectilinear Blocks

Tetsuo ASANO  

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


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



Summary: 
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.