scientific article; zbMATH DE number 1017008
arrangementscombinatorial geometryconvex setsconvexitycoveringsdensitygraph theorypackingspolygonal approximations
Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Exact enumeration problems, generating functions (05A15) Other designs, configurations (05B30) Research exposition (monographs, survey articles) pertaining to convex and discrete geometry (52-02) Analysis of algorithms and problem complexity (68Q25)
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 \textit{H. Edelsbrunner}'s book [Algorithms in combinatorial geometry, EATCS Monographs on Theoretical Computer Science, Vol. 10. Springer-Verlag (1987; Zbl 0634.52001)] or \textit{P. K. Agarwal} and \textit{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 \textit{N. Alon} and \textit{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.
- Unit distances and diameters in Euclidean spaces
- Maximum number of edges joining vertices on a cube
- Extremal problems on triangle areas in two and three dimensions
- Hitting sets when the VC-dimension is small
- A note on a problem of Erdős on right angles
- On the independence number of minimum distance graphs
- Covering the plane with copies of a convex disk
- Separable partitions
- An applied point pattern matching problem: Comparing 2D patterns of protein spots
- Cardinalities of k-distance sets in Minkowski spaces
- Colouring proximity graphs in the plane
- The multiplicity of the two smallest distances among points
- Popular distances in 3-space
- Plane graphs with straight edges whose bounded faces are acute triangles
- On distinct sums and distinct distances.
- Speeding up the incremental construction of the union of geometric objects in practice.
- Configurations between geometry and combinatorics.
- On uniformly distributed dilates of finite integer sequences
- Bichromatic lines with few points
- A new lower bound for the bipartite crossing number with applications
- Convexity and sumsets
- Embedding a set of rational points in lower dimensions
- On the maximum number of touching pairs in a finite packing of translates of a convex body
- On the combinatorics of projective mappings
- Diameters of random distance graphs
- Coverings: variations on a result of Rogers and on the epsilon-net theorem of Haussler and Welzl
- On triangle cover contact graphs
- Realizability of graphs as triangle cover contact graphs
- Periodicity of identifying codes in strips
- The minimal volume of simplices containing a convex body
- Approximating a convex body by a polytope using the epsilon-net theorem
- Antipodality properties of finite sets in Euclidean space
- Methods of combinatorial geometry in action
- On finding maximum-cardinality symmetric subsets
- Monotone paths in line arrangements
- An efficient \(k\) nearest neighbors searching algorithm for a query line.
- The structure and number of global roundings of a graph
- Ball and spindle convexity with respect to a convex body
- A center transversal theorem for hyperplanes and applications to graph drawing
- Chromatic numbers of spaces with forbidden monochromatic triangles
- Covering a rectangle with six and seven circles
- Remarks on superstrings, fractal gravity, Nagasawa's diffusion and Cantorian spacetime
- A combinatorial problem on polynomials and rational functions
- Note on geometric graphs
- On grids in point-line arrangements in the plane
- Centering koebe polyhedra via Möbius transformations
- Discrete harmonic functions on infinite penny graphs
- New Turán type bounds for Johnson graphs
- Disjointness through the lens of Vapnik-Chervonenkis dimension: sparsity and beyond
- Combinatorial spaces
- Separating circles on the sphere by polygonal tilings
- A product inequality for extreme distances
- Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location
- Estimate of the number of edges in special subgraphs of a distance graph
- System of unbiased representatives for a collection of bicolorings
- On arrangements of orthogonal circles
- Random polytopes and the wet part for arbitrary probability distributions
- On packing \(\mathbb R^3\) with thin tori
- Noncrossing monochromatic subtrees and staircases in 0-1 matrices
- Packing and covering with centrally symmetric convex disks
- Minimum vertex cover in ball graphs through local search
- One problem on geometric Ramsey numbers
- On threshold probability for the stability of independent sets in distance graphs
- On the shortest separating cycle
- Edge integrity of nearest neighbor graphs and separator theorems
- The number of edges in induced subgraphs of some distance graphs
- On n-dependence
- A lower bound on opaque sets
- New upper bounds for the independence numbers of graphs with vertices in \(\{-1,0,1\}^n\) and their applications to problems of the chromatic numbers of distance graphs
- Sets with few distinct distances do not have heavy lines
- Systems of distant representatives in Euclidean space
- New upper bound for the chromatic number of a random subgraph of a distance graph
- The packing density of the \(n\)-dimensional cross-polytope
- Lower bounds for the chromatic numbers of distance graphs with large girth
- On some monotone path problems in line arrangements
- On the chromatic number of some geometric type Kneser graphs
- Approximating set multi-covers
- Shallow packings, semialgebraic set systems, macbeath regions, and polynomial partitioning
- Vulnerability of nearest neighbor graphs
- Colorings of the space \(\mathbb R^{n}\) with several forbidden distances
- A combinatorial theorem on labeling squares with points and its application
- The shortest distance among points in general position.
- Independent set of intersection graphs of convex objects in 2D
- Nearly equal distances and Szemerédi's regularity lemma
- A PTAS for a disc covering problem using width-bounded separators
- Excursions into combinatorial geometry
- Traveling the boundary of Minkowski sums.
- Independence numbers and chromatic numbers of some distance graphs
- A semi-algebraic version of Zarankiewicz's problem
- Discrete geometry on colored point sets in the plane -- a survey
- The smallest convex k-gon containing n congruent disks
- Drawing outerplanar graphs using thirteen edge lengths
- The Szemerédi-Trotter theorem in the complex plane
- Six topics on inscribable polytopes
- On large subgraphs with small chromatic numbers contained in distance graphs
- A polynomial regularity lemma for semialgebraic hypergraphs and its applications in geometry and property testing
- Independence numbers of random subgraphs of a distance graph
- Combinatorics and Algebra of Geometric Subdivision Operations
- Areas of triangles and Beck's theorem in planes over finite fields
- scientific article; zbMATH DE number 431994 (Why is no real title available?)
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4339095)
