On Minimum Width Packing of Rectilinear Blocks
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.
- Publication
- IEICE TRANSACTIONS on transactions Vol.E68-E No.10 pp.647-649
- Publication Date
- 1985/10/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- LETTER
- Category
- Communication Theory
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Tetsuo ASANO, "On Minimum Width Packing of Rectilinear Blocks" in IEICE TRANSACTIONS on transactions,
vol. E68-E, no. 10, pp. 647-649, October 1985, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/transactions/10.1587/e68-e_10_647/_p
Copy
@ARTICLE{e68-e_10_647,
author={Tetsuo ASANO, },
journal={IEICE TRANSACTIONS on transactions},
title={On Minimum Width Packing of Rectilinear Blocks},
year={1985},
volume={E68-E},
number={10},
pages={647-649},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={October},}
Copy
TY - JOUR
TI - On Minimum Width Packing of Rectilinear Blocks
T2 - IEICE TRANSACTIONS on transactions
SP - 647
EP - 649
AU - Tetsuo ASANO
PY - 1985
DO -
JO - IEICE TRANSACTIONS on transactions
SN -
VL - E68-E
IS - 10
JA - IEICE TRANSACTIONS on transactions
Y1 - October 1985
AB - 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.
ER -
English
