×

Combinatorial geometry. (English) Zbl 0881.52001

Wiley-Interscience Publication. New York, NY: John Wiley & Sons. xiii, 354 p. (1995).
I cannot help mention rightaway how much fun reading this book is. It provides a unified lighting of several results in combinatorics and geometry from the point of view of packings and coverings in the first part, to that of arrangements in the second. Either part can serve as a very good support for a graduate course (that is actually how the book was conceived), and will offer students with already good mathematical skills invaluable introduction through simple proofs and historical remarks scattered throughout the text.
The contents is organised in two parts. The first part is concerned with packing and covering of convex sets. First, the links with the geometry of numbers (Minkowsky’s theorem) is shown, and the properties of polygonal approximations of a convex set derived. The rest of this part is dedicated to the study of the density of packings (resp. coverings), with extremal properties, upper (resp. lower) bounds and constructions. Finally, a chapter shows the connection between circle packings and planar graphs (Koebe’s theorem, linear embedding, planar separators). All the proofs of the main theorem are given in a synthetic way but remain very accessible.
The second part gives a very readable account of combinatorial geometry, as exposed in part for instance in H. Edelsbrunner’s book [Algorithms in combinatorial geometry, EATCS Monographs on Theoretical Computer Science, Vol. 10. Springer-Verlag (1987; Zbl 0634.52001)] or P. K. Agarwal and M. Sharir’s book [Davenport-Schinzel sequences and their geometric applications, Cambridge Univ. Press (1995; Zbl 0834.68113)]. It contains a discussion of the complexity of various geometric (portions of) arrangements, of extremal and geometric graph theory, and of discrepancy and the Vapnik-Chervonenkis dimension.
Overall, the material in this book was sometimes previously not published, or in different sources with different preoccupations. The main asset of this book is to present a vast collection of seemingly unrelated results with a continuous line of attack and similar ideas. Its reading can be most usefully combined with that of N. Alon and J. H. Spencer’s book [The probabilistic method, John Wiley & Sons, NY (1992; Zbl 0767.05001)], which is interestingly in the references but not cited in the preface’s otherwise useful and comprehensive list of related books and surveys.

MSC:

52-02 Research exposition (monographs, survey articles) pertaining to convex and discrete geometry
05-02 Research exposition (monographs, survey articles) pertaining to combinatorics
05B30 Other designs, configurations
05A15 Exact enumeration problems, generating functions
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite

Online Encyclopedia of Integer Sequences:

Expansion of x*(1+x^4)/((1-x)^2*(1-x^4)).