Random Sequential Packing of Cubes

The following sections are included:

• Preface

• Contents

The classical packing problem is the sphere packing problem, i.e. the problem of putting balls of the same radius in Euclidean space ℝⁿ and maximize its density, i.e. minimize the volume of the interstitial space. The 2-dimensional sphere packing problem is solved by the hexagonal sphere packing [Lagrange (1773); Thue (1910); Zong (1999)]…

The following sections are included:

• One-dimensional discrete random sequential packing

• Application of generating function

• Number of gaps

• Minimum of gaps

• Packing on circle and numerical study

• Appendix: Complex Analysis

The following sections are included:

• The probabilistic setup of the problem

• The solution of the delay differential equation using Laplace transform

• The computation of the limit

• Packing on circle and the speed of convergence

• Appendix: The Laplace transform

The following sections are included:

• Main properties of Pr(L(x) ≥ h)

• Laplace transform of Pr(L(x) ≥ h)

• Numerical calculations for a(h)

• Asymptotic analysis for a(h)
  • Renewal equation technique
  • Approximation for small 1 – h
  • Approximation for small h

• Maximum of gaps

• Appendix: Renewal equations

The following sections are included:

• Estimating M(x) – C_Rx

• The variance and the central limit theorem

The following sections are included:

• Random sequential bisection

• Binary search tree

• Expected number of nodes at the d-th level

• Exponential distribution and uniform distribution

• Asymptotic size of the associated tree

• Asymptotic shape of the associated tree

• More on the associated tree

The following sections are included:

• The limit random packing density

• Expectation and variance of number of cars for l = 0

• The central limit theorem

• Almost sure convergence results

• The limit distribution of a randomly chosen gap

The following sections are included:

• Integral equations

• Existence of the limit packing density

• Laplace transform and explicitly solvable cases

• General solution methods

• The power series solution

• Numerical computations

The following sections are included:

• Sequential random packing and the covering problem

• Random packing of spheres

• Random packing of cubes

• Random sequential coding by Hamming distance

• Frequency of getting Golay code by a random sequential packing

The following sections are included:

• Setting of a goal

• Reduction to another problem

• Proof of the theorem

The following sections are included:

• Introduction

• Algorithm for generating cube packings

• Non-extensible cube packings

• The second moment

• Appendix: Crystallographic groups

The following sections are included:

• Introduction

• Combinatorial cube packings

• Discrete random cube packings of the cube

• Combinatorial torus cube packings and lamination construction

• Properties of non-extensible cube packings

The following sections are included:

• Appendix A: Combinatorial Enumeration

• Bibliography

• Index