## 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 C_{n} of items in a maximum cardinality disjoint subset of n random rectangles satisfies n^{1/2}/K ≤ EC_{n} ≤ 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 ≤ EC_{n} ≤ 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+1)}/K ≤ EQ_{n} ≤ Kn^{d/(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