Packing random rectangles (Q5952007): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 02:05, 30 January 2024
scientific article; zbMATH DE number 1687557
Language | Label | Description | Also known as |
---|---|---|---|
English | Packing random rectangles |
scientific article; zbMATH DE number 1687557 |
Statements
Packing random rectangles (English)
0 references
2 May 2002
0 references
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] .\) The authors prove that the number C\(_{n} \) of items in a maximum cardinality disjoint subset of \(n\) random rectangles satisfies \(\frac{n^{1/2}}{K}\leq EC_{n}\leq Kn^{1/2}\), where \(K\) is an absolute constant. Although tight bounds for the problem generalized to \(d >2\) dimensions remain an open problem, the authors show that, for some absolute constant \(K\), \(\frac{n^{1/2}}{K}\leq EC_{n}\leq K(n\log ^{d-1}n)^{1/2}.\) Finally, for a certain distribution of random cubes, the authors show that for some absolute constant \(K\), the number \(Q_{n}\) of items in a maximum cardinality disjoint subset of the cubes satisfies \(\frac{n^{d/(d+1)}}{K}\leq EQ_{n}\leq Kn^{d/(d+1)}.\)
0 references
random rectangles
0 references