DIMACS TR: 99-44

Packing Random Rectangles

Authors: E. G. Coffman, George S. Lueker, Joel Spencer, and Peter M. Winkler


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 of items in a maximum cardinality disjoint subset of n random rectangles has the tight asymptotic bound Theta(n^{1/2}). Although tight bounds for the problem generalized to d>2 dimensions remain an open problem, we are able to show that Omega(n^{1/2}) and O((n log^{d-1}n)^{1/2}) are asymptotic lower and upper bounds. In addition, we prove that Theta(n^{d/(d+1)}) is a tight asymptotic bound for the case of random cubes.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1999/99-44.ps.gz
DIMACS Home Page