Packing rectangles and intervals^∗

^∗Research supported in part by NSA

Abstract

Consider a parameter α>0, and a large integer AT. Assume that for P≥1, we are given a family I _p of [2^-αp N] random intervals of [0,1], and consider the union I of the families I_p . A packing of I is a disjoint sub family of I. The cost of the packing is the sum of the wasted space (the measure of the part of [0,1] not covered by the packing) and the costs of the intervals of the packing, where, if l∊ I_p , the cost of I is 2^-p |I|. We estimate as a function of N, the expected value of the cost of an optimal packing. We discover the very surprising fact that (up to terms of smaller order) this cost behaves as N ^-1/2 for all 1≤α≤2. This problem is motivated by a problem of packing random rectangles.

Keywords:

• Random Rectangle Packing
• Interval Packing
• Optimal Packing

C.R. Categories:

• F2.2

^∗Research supported in part by NSA

^†Corresponding author [email protected]

^∗Research supported in part by NSA

^†Corresponding author [email protected]

Notes

^∗Research supported in part by NSA

^†Corresponding author [email protected]