组合几何是一门古老而又年轻的数学学科,许多组合几何问题因其直观表述而独具魅力。计算机科学的迅猛发展大大促进了组合几何的发展,也为组合几何开拓了广阔的应用前景。本书系统阐述组合几何领域近三十余年来若干最为重要的研究成果与方法,并给出详尽证明。本书涵盖数的几何、填充与覆盖、极图理论、超图理论、有限点集距离分布、几何图论、几何偏差理论等多个分支,每章配有习题与解答提示。
原书作者特地为中文版撰写了反映1995年本书英文版出版以来最新研究成果的补充内容,提供了大量最新参考文献。
本书可用作数学与计算机科学有关专业的教材与科研用书,也可供组合几何爱好者赏析阅读,还可供计算几何、计算机图形学、编码理论、机器人技术及计算机辅助设计等应用领域的专业人员参考。
样章试读
目录
- 中文版序
英文版原序
第一部分 凸集的配置
第1章 数的几何
1. 1格
1.2 二平方和定理与四平方和定理
习题
第2章 凸体的多边形逼近
2.1 Dowker定理
2.2 椭圆的一个极值性质
2.3 凸体的多胞形逼近
习题
第3章 全等凸体形成的填装与覆盖
3.1 凸体形成的填装
3.2 凸体形成的覆盖
3.3 填装和覆盖的关系
习题
第4章 格填装与格覆盖
4.1 Fary定理
4.2 双格填装
习题
第5章 胞腔分解方法
5.1 Dirichlet-Voronoi胞腔
5.2 阴影胞腔
习题
第6章 Blichfeldt方法与Rogers方法
6.1 Blichfeldt放大法
6.2 Rogers单纯形界
6.3 球填装的截面
习题
第7章 有效随机配置
7.1 Minkowski-Hlawka定理
7. 2 空间中的稠密格填装
7.3 格填装与码
7.4 空间中的稀疏覆盖
习题
第8章 圆盘填装与平面图
8.1 Koebe表示定理
8.2 Lipton-Tarjan分离子定理
8.3离散凸函数
习题
第二部分 点与直线的配置
第9章 极图理论
9. 1 禁用路与圈
9.2 禁用完全子图
9.3 Erdos-Stone定理
9.4 Ramsey-Szemerédi定理
9.5两个几何应用
习题
第10章空间中的重复距离
10.1平面中的单位距离
10.2空间中的单位距离
10.3均匀超图
10.4平面中的近相等距离
10.5集合的小子集所确定的互异距离
习题
第11章 直线的配置
11.1 直线配置的剖分
11.2 胞腔集的复杂度
习题
第12章 关联数上下界的应用
12.1 平面中的重复角
12.2 无重复距离的子集
12.3 有界自由度曲线族
12.4 球面上的重复距离
12.5 点确定的互异距离
习题
第13章 再论重复距离
13.1 处于凸位置的点集
13.2 处于一般位置的点集
13.3 最小距离与最大距离
13.4 Borsuk问题
习题
第14章 几何图
14.1 禁用几何子图
14.2 偏序集
14.3 交叉边
14.4 交叉数与对分宽度
14.5 交叉数与关联数
习题
第15章 ε网格与超图的横截
15.1 横截与分数横截
15.2 Vapnik-Chervonenkis维数
15.3 范围空间与ε网格
15.4 小穿刺数的生成树
15.5 范围搜索
习题
第16章 几何偏差
16.1 浮动着色法
16.2 偏差与VC维数
16.3 部分着色方法
16.4 偏差与积分几何
16.5 偏差与ε逼近
习题
习题提示
参考文献
符号索引
作者索引
主题索引