DIMACS TR: 99-44
Packing Random Rectangles
Authors: E. G. Coffman, George S. Lueker, Joel Spencer, and Peter M. Winkler
ABSTRACT
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