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 Cn of items in a maximum cardinality disjoint subset of n random rectangles satisfies n1/2/K ≤ ECn ≤ Kn1/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, n1/2/K ≤ ECn ≤ K (n logd-1 n)1/2. Finally, for a certain distribution of random cubes we show that for some absolute constant K, the number Qn of items in a maximum cardinality disjoint subset of the cubes satisfies nd/(d+1)/K ≤ EQn ≤ Knd/(d+1).
Original language | English (US) |
---|---|
Pages (from-to) | 585-599 |
Number of pages | 15 |
Journal | Probability Theory and Related Fields |
Volume | 120 |
Issue number | 4 |
DOIs | |
State | Published - Aug 2001 |
Keywords
- 2-dimensional packing
- Independent sets
- Intersection graphs
- Probabilistic analysis of optimization problems
- n-dimensional packing
ASJC Scopus subject areas
- Analysis
- Statistics and Probability
- Statistics, Probability and Uncertainty