@inproceedings{61028829b0f74b07ad761b74260515cb,
title = "Average-case analysis of rectangle packings",
abstract = "We study the average-case behavior of algorithms for finding a maximal disjoint subset of a given set of rectangles. In the probability model, a random rectangle is the product of two independent random intervals, each being the interval between two points drawn uniformly at random from [0, 1]. We have proved that the expected cardinality of a maximal disjoint subset of n random rectangles has the tight asymptotic bound θ(n1/2). Although tight bounds for the problem generalized to d > 2 dimensions remain an open problem, we have been able to show that ω(n1/2) and O((n logd-1 n)1/2) are asymptotic lower and upper bounds. In addition, we can prove that θ(nd/(d+1)) is a tight asymptotic bound for the case of random cubes.",
author = "Coffman, {E. G.} and Lueker, {George S.} and Joel Spencer and Winkler, {Peter M.}",
year = "2000",
doi = "10.1007/10719839_30",
language = "English (US)",
isbn = "3540673067",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "292--297",
booktitle = "LATIN 2000",
note = "4th Latin American Symposium on Theoretical Informatics, LATIN 2000 ; Conference date: 10-04-2000 Through 14-04-2000",
}