马陶塞克编著的《离散几何讲义（英文影印版）》旨在为读者提供一本学习离散几何的引入教程，主要内容包括凸集，凸多面体和超平面的安排；几何构型的组合复杂性；交叉模型和凸集的截面；几何ramsey型结果；有限几何空间嵌入到赋范空间等。在好多应用领域，都可以涉及到这里的很多结果和方法。目次：凸性；点格和minkowski定理；凸独立子集；事件问题；凸多面体；下包络；凸集的相交模型；几何选择定理；计数k-集；高维多面体的两个应用；高维中的体积；测度集聚和球面集；嵌入有限度量空间到赋范空间。

preface

notation and terminology

1 convexity

 1.1 linear and affine subspaces, general position

 1.2 convex sets, convex combinations, separation

 1.3 radon's lemma and helly's theorem

 1.4 centerpoint and ham sandwich

2 lattices and minkowski's theorem

 2.1 minkowski's theorem

 2.2 general lattices

 2.3 an application in number theory

3 convex independent subsets

 3.1 the erdos-szekeres theorem

 3.2 horton sets

4 incidence problems

 4.1 formulation

 4.2 lower bounds: incidences and unit distances.

 4.3 point-line incidences via crossing numbers

 4.4 distinct distances via crossing numbers

 4.5 point-line incidences via cuttings

 4.6 a weaker cutting lemma

 4.7 the cutting lemma: a tight bound

5 convex polytopes

 5.1 geometric duality

 5.2 h-polytopes and v-polytopes

 5.3 faces of a convex polytope

 5.4 many faces: the cyclic polytopes

 5.5 the upper bound theorem

 5.6 the gale transform

 5.7 voronoi diagrams

6 number of faces in arrangements

 6.1 arrangements of hyperplanes

 6.2 arrangements of other geometric objects

 6.3 number of vertices of level at most k

 6.4 the zone theorem

 6.5 the cutting lemma revisited

7 lower envelopes

 7.1 segments and davenport-schinzel sequences

 7.2 segments: superlinear complexity of the lower envelope.

 7.3 more on davenport-schinzel sequences

 7.4 towards the tight upper bound for segments

 7.5 up to higher dimension: triangles in space

 7.6 curves in the plane

 7.7 algebraic surface patches

8 intersection patterns of convex sets

 8.1 the fractional helly theorem

 8.2 the colorful carath~odory theorem

 8.3 tverberg's theorem

9 geometric selection theorems

 9.1 a point in many simplices: the first selection lemma

 9.2 the second selection lemma

 9.3 order types and the same-type lemma

 9.4 a hypergraph regularity lemma

 9.5 a positive-fraction selection lemma

10 transversals and epsilon nets

 10.1 general preliminaries: transversals and matchings

 10.2 epsilon nets and vc-dimension

 10.3 bounding the vc-dimension and applications

 10.4 weak epsilon nets for convex sets

 10.5 the hadwiger-debrunner (p, q)-problem

 10.6 a (p, q)-theorem for hyperplane transversals

11 attempts to count k-sets

 11.1 definitions and first estimates

 11.2 sets with many halving edges

 11.3 the lovfisz lemma and upper bounds in all dimensions

 11.4 a better upper bound in the plane

12 two applications of high-dimensional polytopes

 12.1 the weak perfect graph conjecture

 12.2 the brunn-minkowski inequality

 12.3 sorting partially ordered sets

13 volumes in high dimension

 13.1 volumes, paradoxes of high dimension, and nets

 13.2 hardness of volume approximation

 13.3 constructing polytopes of large volume

 13.4 approximating convex bodies by ellipsoids

14 measure concentration and almost spherical sections

 14.1 measure concentration on the sphere

 14.2 isoperimetric inequalities and more on concentration

 14.3 concentration of lipschitz functions

 14.4 almost spherical sections: the first steps

 14.5 many faces of symmetric polytopes

 14.6 dvoretzky's theorem

15 embedding finite metric spaces into normed spaces

 15.1 introduction: approximate embeddings

 15.2 the johnson-lindenstranss flattening lemma

 15.3 lower bounds by counting

 15.4 a lower bound for the hamming cube

 15.5 a tight lower bound via expanders

 15.6 upper bounds for ~oo-embeddings

 15.7 upper bounds for euclidean embeddings

what was it about? an informal summary

hints to selected exercises

bibliography

index