PACKING SOFT RECTANGLES
Hiroshi Nagamochi · International Journal of Foundations of Computer Science · 2006
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, …, rn 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 a amax = max 1≤i≤n a(ri), then these n soft rectangles can be packed inside R so that the apect ratio of each rectangle ri is at most 3.