New approaches to circle packing in a square. With program codes. (Q855072)

The book under review gives a detailed survey on the achievements of the last years on the problem of finding densest packings of a given number \(n\) of congruent circles in a unit square, say. The nice and easy formulation of the problem contrasts with the difficulty of finding solutions. In many instances, an optimal solution is not unique and it can have a surprising structure, e.g., it contains a ``free'' circle which can be moved slightly without loosing the optimality. The more general problem of packing equal circles in a given bounded subset of the plane has a long history in discrete geometry which is presented in the first chapter of the book. Here the authors give a stimulating summary on the existing results along with many interesting examples of circle packings in art, religion and history. The main purpose of this book, however, is to provide theoretical as well as computational results on that packing problem which have been obtained in the last years. To this end the authors give in the second chapter different geometric formulations of the packing problem and they describe possible mathematical programming models. Due to complexity and numerical instability of these global optimization problems one can not expect to obtain reliable optimal solutions via this straightforward computational approach, at least for large \(n\). Therefore, one is mainly interested in finding good approximate circle packings for which one can prove that they are optimal up to a very small error tolerance. Different approaches following that scheme as well as the reliability of the numerical results obtained by their implementation are discussed in detail in the next chapters. The source code of the used programs is contained on an enclosed CD, inviting the reader to take part in the search for new optimal or ``better'' packings. The text is written in a very comprehensive and informative way, and all the numerical results on densities are impressively illustrated by many figures of ``optimal'' packings. In fact, in the appendix pictures and densities of currently best known packings for \(n\leq 200\) circles are given. The book will serve as an excellent source for everybody, expert on non-expert, who is interested in circle packing or, who is just interested in the hardness of an appealing problem in discrete geometry.