|
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
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)>>
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.
|
|
|