Packing and covering.

*(English)*Zbl 0176.51401
Cambridge Tracts in Mathematics and Mathematical Physics. No. 54. Cambridge: University Press. viii, 111 p. (1964).

This book deals with packings and coverings of convex sets in \(\mathbb R^n\), a topic inspired by the Geometry of Numbers, but arithmetic connections are not discussed here. The author feels that most of the simplest general results in this field have been discovered, thus a report on them is indicated. The approach of the book is a compromise between historical development, and the systematical one, which makes it refreshing and readable.

Given a set \(K\) in \(\mathbb R^n\) (the only space considered in the book), introduce \(K+x= \{y\in \mathbb R^n;\;y=k+x\), with \(k\in K\}\), and call it a translate of \(K\). A collection \(\mathcal K = \{K+x_i,\;i\in I\}\) of translates is a packing, if no two sets have common inner points, and a covering, if their union is the space. If \(x_i\) runs through the points of a lattice \(\Lambda = \{m_1a_1+\dots+m_na_n, \)a_j\in \Bbb R^n}\( linearly independent, \)m_j\( integers\)}\(, we call \)\cal K\( lattice packing or covering. Set \)\rho_+(K, C) = \mu(C)^{-1} \sum \mu(K + x_i)\(, where \)C\( is a half-closed cube parallel to the axes, and the sum is taken over the \)x_i\('s such that \)C\cap (K+x_i)\ne \emptyset\( \)(\mu(K)\ne 0)\(. \)\rho_+(K) = \limsup \rho_+(K,C)\(, where \)\limsup\( is taken over all such cubes, when the edge tends to infinity. \)\rho_{-}\( is defined similarly (with coverings in mind), so that, if \)K\( is a packing \)\rho_+(K)\le 1\(, and, if it is a covering, \)\rho_{-}(K)\ge 1\(. Then \)\delta(K)\(, \)\delta_L(K)\( \)(\vartheta(K), \vartheta_L(K))\( denotes the sup (inf) of densities over all packings and all lattice packings (over all coverings, and lattice coverings). The main topics of the book are then some inequalities for these functions for convex sets, and for particular sets (spheres, simplexes, cylinders, etc.). The difference set, \)DK = {x\in \Bbb R^n: x=y-z, y,z\in K}\( is centrally symmetric, and \)\delta_L(K)\( and \)\delta_L(DK)\(, etc., are simply related to one another. It is established, that \)\mu(DK)\le \binom{2n}{n} \mu(K)\(. \par The existence of reasonably dense packings of arbitrary convex sets, as well as reasonably economical coverings are established. For both \)\delta(K)\( and \)\delta_L(K)\( the inequalities \)\(\delta(K)\geq 2(n!)^2/(2n)! \quad\text{and}\quad \delta_L(K)\leq n^{\log_2n + c \log \log n}\)\( are proven. \par A number \)\sigma_n\( is geometrically introduced (as the ratio of the volume covered by unit spheres centered to the vertices of a regular simplex of edge 2 to that of the volume of the simplex), and for spheres \)K\(, \)\delta(K)\le\sigma_n\( is proved. A \)\tau_n\( is defined dually, and \)\vartheta(E)\ge \tau_n\( is proven. \par The following partial list of chapter and section titles of the book will indicate some more questions covered: The historical outline of the theories of packings and coverings, in particular lattice packings of spheres (exact values in dimensions \)\le 8\(, good estimates in dimensions \)\le 12\(, and the best, general estimates of Blichfeldt, Rogers and Davenport); lattice packings of convex sets; packings and coverings by convex sets; packings of simplices cannot be very dense; packings of spheres cannot be very dense: the Voronoi polyhedra; the inequalities of Blichfeldt; densities of packings of spheres; Daniel's asymptotic formula. Coverings with spheres cannot be very economical: the dual subdivision; the solid angle of a simplex; coverings of space with spheres.\)

Given a set \(K\) in \(\mathbb R^n\) (the only space considered in the book), introduce \(K+x= \{y\in \mathbb R^n;\;y=k+x\), with \(k\in K\}\), and call it a translate of \(K\). A collection \(\mathcal K = \{K+x_i,\;i\in I\}\) of translates is a packing, if no two sets have common inner points, and a covering, if their union is the space. If \(x_i\) runs through the points of a lattice \(\Lambda = \{m_1a_1+\dots+m_na_n, \)a_j\in \Bbb R^n}\( linearly independent, \)m_j\( integers\)}\(, we call \)\cal K\( lattice packing or covering. Set \)\rho_+(K, C) = \mu(C)^{-1} \sum \mu(K + x_i)\(, where \)C\( is a half-closed cube parallel to the axes, and the sum is taken over the \)x_i\('s such that \)C\cap (K+x_i)\ne \emptyset\( \)(\mu(K)\ne 0)\(. \)\rho_+(K) = \limsup \rho_+(K,C)\(, where \)\limsup\( is taken over all such cubes, when the edge tends to infinity. \)\rho_{-}\( is defined similarly (with coverings in mind), so that, if \)K\( is a packing \)\rho_+(K)\le 1\(, and, if it is a covering, \)\rho_{-}(K)\ge 1\(. Then \)\delta(K)\(, \)\delta_L(K)\( \)(\vartheta(K), \vartheta_L(K))\( denotes the sup (inf) of densities over all packings and all lattice packings (over all coverings, and lattice coverings). The main topics of the book are then some inequalities for these functions for convex sets, and for particular sets (spheres, simplexes, cylinders, etc.). The difference set, \)DK = {x\in \Bbb R^n: x=y-z, y,z\in K}\( is centrally symmetric, and \)\delta_L(K)\( and \)\delta_L(DK)\(, etc., are simply related to one another. It is established, that \)\mu(DK)\le \binom{2n}{n} \mu(K)\(. \par The existence of reasonably dense packings of arbitrary convex sets, as well as reasonably economical coverings are established. For both \)\delta(K)\( and \)\delta_L(K)\( the inequalities \)\(\delta(K)\geq 2(n!)^2/(2n)! \quad\text{and}\quad \delta_L(K)\leq n^{\log_2n + c \log \log n}\)\( are proven. \par A number \)\sigma_n\( is geometrically introduced (as the ratio of the volume covered by unit spheres centered to the vertices of a regular simplex of edge 2 to that of the volume of the simplex), and for spheres \)K\(, \)\delta(K)\le\sigma_n\( is proved. A \)\tau_n\( is defined dually, and \)\vartheta(E)\ge \tau_n\( is proven. \par The following partial list of chapter and section titles of the book will indicate some more questions covered: The historical outline of the theories of packings and coverings, in particular lattice packings of spheres (exact values in dimensions \)\le 8\(, good estimates in dimensions \)\le 12\(, and the best, general estimates of Blichfeldt, Rogers and Davenport); lattice packings of convex sets; packings and coverings by convex sets; packings of simplices cannot be very dense; packings of spheres cannot be very dense: the Voronoi polyhedra; the inequalities of Blichfeldt; densities of packings of spheres; Daniel's asymptotic formula. Coverings with spheres cannot be very economical: the dual subdivision; the solid angle of a simplex; coverings of space with spheres.\)

Reviewer: I. Fary

##### MSC:

52-01 | Introductory exposition (textbooks, tutorial papers, etc.) pertaining to convex and discrete geometry |

52-02 | Research exposition (monographs, survey articles) pertaining to convex and discrete geometry |

52C15 | Packing and covering in \(2\) dimensions (aspects of discrete geometry) |

52C17 | Packing and covering in \(n\) dimensions (aspects of discrete geometry) |

05B40 | Combinatorial aspects of packing and covering |

11H31 | Lattice packing and covering (number-theoretic aspects) |