Packing random rectangles (Q5952007)

A random rectangle is the product of two independent random intervals, each being the interval between two random points drawn independently and uniformly from \([ 0,1] .\) The authors prove that the number C\(_{n} \) of items in a maximum cardinality disjoint subset of \(n\) random rectangles satisfies \(\frac{n^{1/2}}{K}\leq EC_{n}\leq Kn^{1/2}\), where \(K\) is an absolute constant. Although tight bounds for the problem generalized to \(d >2\) dimensions remain an open problem, the authors show that, for some absolute constant \(K\), \(\frac{n^{1/2}}{K}\leq EC_{n}\leq K(n\log ^{d-1}n)^{1/2}.\) Finally, for a certain distribution of random cubes, the authors show that for some absolute constant \(K\), the number \(Q_{n}\) of items in a maximum cardinality disjoint subset of the cubes satisfies \(\frac{n^{d/(d+1)}}{K}\leq EQ_{n}\leq Kn^{d/(d+1)}.\)