論文

査読有り
2006年10月

Packing soft rectangles

International Journal of Foundations of Computer Science
  • Hiroshi Nagamochi

17
5
開始ページ
1165
終了ページ
1178
記述言語
英語
掲載種別
研究論文(学術雑誌)
DOI
10.1142/S0129054106004327

Let R be a rectangle with given area a(R), height h(R) and width w(R), and r1, r2,..., rn be n soft rectangles, where we mean by a soft rectangle a rectangle r whose area a(r) is prescribed but whose aspect ratio ρ(r) is allowed to be changed. In this paper, we consider the problem of packing n soft rectangles r1, r2,..., r n into R. We prove that, if a(R) ≥ ∑1≤i≤n a(ri) + 0.10103amax and amax ≤ 3(min{h(R), w(R)})2 hold for amax = max1≤i≤n a(r i), then these n soft rectangles can be packed inside R so that the apect ratio of each rectangle ri is at most 3. © World Scientific Publishing Company.

リンク情報
DOI
https://doi.org/10.1142/S0129054106004327
ID情報
  • DOI : 10.1142/S0129054106004327
  • ISSN : 0129-0541
  • SCOPUS ID : 33748799667

エクスポート
BibTeX RIS