Expected wasted space of optimal simple rectangle packing

DOI10.1007/S00440-003-0299-6MaRDI QIDQ1769075zbMATH OpenOpenAlexFDO

Authors Michel Talagrand

Publication date 17 March 2005

Published in Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00440-003-0299-6

zbMATH Keywords

Poisson point processrectangle packing

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05)

Review text

Random rectangles are packed in the unit square without overlapping and with the additional property called ``simple, which means that each vertical line can intersect at most one rectangle. This paper aims at improving the result of \textit{W. T. Rhee} [Ann. Appl. Probab. 10, 539--548 (2000; Zbl 1051.60012)] for the expected waste space of optimal simple rectangle packing in the unit square. The main result states that the expected waste space \(E(W_n)\) (\(n\) being the rectangles packed) satisfies \(\log E(W_n) = -\frac12\log n + \sqrt{\log 2\log n}+O(\log\log n)\).

Recommendations

• Optimal rectangle packing
• On rectangle packing, maximizing benefits
• Optimal rectangle packing: an absolute placement approach
• Algorithms and Computation
• Publication:4508386
• Packing rectangles into the unit square
• On packing of rectangles in a rectangle
• A least wasted first heuristic algorithm for the rectangular packing problem
• Efficient packing of unit squares in a square
• Optimal packings of unit squares in a square

Cites work

• scientific article; zbMATH DE number 52589 (Why is no real title available?)
• scientific article; zbMATH DE number 1340282 (Why is no real title available?)
• Packing random intervals
• Packing random intervals
• Packing Random Rectangles of Given Volume
• Packing rectangles and intervals^∗
• The random weighted interval packing problem: The intermediate density case.

Cited in

(4)

• Order of decay of the wasted space for a stochastic packing problem.
• Packing rectangles and intervals^∗
• scientific article; zbMATH DE number 1512697 (Why is no real title available?)
• Packing Random Rectangles of Given Volume

This page was built for publication: Expected wasted space of optimal simple rectangle packing

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