Packing random rectangles

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17) Geometric probability and stochastic geometry (60D05) Discrete location and assignment (90B80)

Review text

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)}.\)

Recommendations

Cited in

(5)

This page was built for publication: Packing random rectangles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5952007)