For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
On Minimum Width Packing of Rectilinear Blocks
IEICE TRANSACTIONS (1976-1990)
Publication Date: 1985/10/25
Print ISSN: 0000-0000
Type of Manuscript: LETTER
Category: Communication Theory
Full Text: PDF(265KB)>>
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.