Packing random rectangles

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]. We prove that the number C-n of items in a maximum cardinality disjoint subset of n random rectangles satisfies n(1/2)/K less than or equal to ECn less than or equal to Kn(1/2,) where K is an absolute constant. Although tight bounds for the problem generalized to d > 2 dimensions remain an open problem, we are able to show that, for some absolute constant K, n(1/2)/K less than or equal to ECn less than or equal to K(n log(d-1) n)(1/2.) Finally, for a certain distribution of random cubes we show that for some absolute constant K, the number Q(n) of items in a maximum cardinality disjoint subset of the cubes satisfies n(d/(d+l))/K less than or equal to EQ(n) less than or equal to K-n(d/(d+l).)