第0章 预备知识 1
0.1算法与数据结构 2
0.1.1算法 2
0.1.2数据结构 5
0.2相关的几何知识 9
0.2.1基本定义 9
0.2.2线性变换群下的不变量 11
0.2.3几何对偶性 12
0.3计算模型 13
第1章 几何查找（检索） 17
1.1点定位问题 18
1.1.1点9是否在多边形P内 19
1.1.2确定点q在平面剖分中的位置 24
1.1.3 Z1.3算法（判定点q在哪个三角形的算法 30
1.2范围查找问题 31
1.2.1多维二叉树(k-D树）的方法 32
1.2.2直接存取方法 34
1.2.3范围树方法 36
1.3判定点集是否在多边形内 37
1.4平面网络的处理与点q的定位 39
1.5平面上链的处理与点q的定位 42
1.6平面上线段的处理与点q的定位 44
第2章 多边形 47
2.1凸多边形 47
2.2简单多边形 53
2.3多边形的三角剖分 58
2.4多边形的凸划分 62
第3章 凸壳及其应用 71
3.1凸壳的基本概念 71
3.2计算平面点集凸壳的算法 75
3.2.1卷包裹法 75
3.2.2格雷厄姆方法 76
3.2.3分治算法 77
3.2.4Z3-1算法与Z3-2算法（求平面点集的凸壳） 79
3.2.5实时凸壳算法 82
3. 2.6增量算法 86
3.2.7近似凸壳算法 87
3.3计算平面多边形顶点凸壳的算法 88
3.4计算平面多边形链顶点凸壳的算法 92
3.4.1概念、算法思想与描述 92
3.4.2解释与时间复杂性 95
3.5计算平面线段集凸壳的算法 96
3.6计算三维空间点集凸壳的算法 104
3.6.1基本概念 104
3.6.2卷包裹法 105
3.6.3分治算法 107
3.6.4 Z3.8算法（三维凸壳） 109
3.6. 5增量算法 111
3.7时间复杂性低于下界O（nlogn）的凸壳算法 112
3.8凸壳的应用 114
3.8.1确定任意多边形的凸、凹顶点 114
3.8.2利用凸壳求解货郎担问题 116
3.8.3凸多边形直径 119
3.8.4连接两个多边形成一条回路 121
第4章Voronoi图、三角剖分及其应用 125
4.1 Voronoi图的基本概念 126
4.2构造Voronoi图的算法 130
4.2.1半平面的交 130
4.2.2增量构造方法 130
4.2.3分治法 134
4.2.4减量算法 136
4.2.5平面扫描算法 137
4.2.6构造最远点意义下Voronoi图的算法 139
4.3平面点集的三角剖分 141
4.3.1平面点集三角剖分的贪心算法 142
4.3.2 Delaunay三角剖分与多边形内部点集的三角剖分 144
4.3.3平面点集三角剖分的算法 146
4.4平面线段集的三角剖分 151
4.5平面点线集的三角剖分 156
4.6平面点集的伪三角剖分 161
4.7三角剖分的表示 169
4.8应用 177
4.8.1最近邻近 177
4.8.2最大化最小角的三角剖分 178
4.8.3最大空圆 178
4.8.4最小生成树 182
4.8.5货郎担问题 183
4.8.6中轴 184
4.8.7 Voronoi图与凸壳的关系 192
4.8.8 Voronoi图的推广 196
4.8.9有约束的Voronoi图 204
4.8.10线段集的Voronoi图 205
4.8.11关联于多边形的Voronoi图 211
4.8.12几何数据压缩 219
4.8.13车辆定位导航系统的新定位算法 224
4.8.14调色 226
4.8.15点集增（删）点之后的三角剖分 227
第5章 交与并及其应用 230
5.1线段交的算法 230
5.2多边形的交 237
5.2.1凸多边形交的算法 237
5.2.2星形多边形交的算法 241
5.2.3任意简单多边形交的算法 243
5.3半平面的交及其应用 245
5.3.1半平面的交 245
5.3.2两个变量的线性规划 246
5.4多边形的并 252
5.5凸多面体的交 258
5.6应用 262
5.6.1地图匹配 262
5.6.2地图数据的处理 267
5.6.3线段与凸多面体面的交 267
第6章 多边形的获取及相关问题 269
6.1连接不相交线段成简单多边形（链） 269
6.2红外图像边缘提取 274
6.3提取可见光图像的边缘 280
6.4图像边界点行排列转换为顺序排列 286
6.5数字图像中目标边界的多边形表示 291
6.6包含密集点、线集多边形的获取 295
6.7满足特定条件的多边形划分 302
6.8多边形与多边形链 304
6.9圆弧、直线段组成的多边形顶点凸、凹性的确定 307
6.10多边形放大、缩小及移动 309
6.11带状多边形的处理 311
6.12下料问题（1） 312
6.13下料问题（2） 320
6.14下料问题（3） 329
6.15线锯问题 333
6.16多边形（链）的匹配 339
第7章 几何体的划分与等分 342
7.1平面上不同类型点集的划分 342
7.2多边形内不同类型点集的等分 352
7.3平面上不同类型线段集的划分 358
7.4平面上不同类型线段集的等分 365
7.5平面上不同类型点线集的划分与等分 367
7.6链、多边形的划分与等分 369
第8章 算法的运动规划 378
8.1最短路径 379
8.1.1可视图及其构造 379
8.1.2 Z8-1算法（寻求网络中任意两点间最短路径的算法） 380
8.1.3多面体面上任意两点之间的最短路径 385
8.1.4货运汽车调度及行驶路径问题 392
8.2移动圆盘 394
8.3平移凸多边形 395
8.4移动杆状机器人 398
8.4.1网格分解 399
8.4.2收缩方法 401
8.5机器人臂的运动 403
8.5. 1可达性 404
8.5.2构造可达性 405
8.6可分离性 408
8.6.1多种可分离性 408
8.6.2借助于平移的可分离性 409
8.6.3分离问题是NP-难的 410
8.6.4模拟河内塔问题 411
8.7满足一定条件的运动规划 412
8.8多边形内点之间的可视图 413
8.9多边形内任意两点之间的最短路径 421
8.10自主车自动定位及确定行车方向 427
第9章 几何拓扑网络设计 432
9.1 G（S）问题 433
9.1.1最大间隙问题（MAX G） 434
9.1.2最小覆盖问题（MIN C） 436
9.1.3 2-中心问题 440
9.1.4 k-中心问题 444
9.1.5最近对问题（CPP） 452
9.1.6所有最近邻近问题（ANNP） 453
9.1.7邮局问题（POFP） 454
9.2 G（E）问题 455
9.2.1 EMST问题 455
9.2.2欧几里得TSP 458
9.2.3欧几里得最大生成树问题（EMXT） 459
" 9.3 G（S,E）问题 460
9.3.1欧几里得Steiner最小树问题（ESMT） 460
9.3.2直线Steiner最小树问题（RSMT） 463
9.3.3求解ESMT问题的算法 464
9.4 G（Ω）问题 470
9.4.1有障碍物的最大空隙问题（MAX G（Ω） ） 471
9.4.2具有障碍物的欧几里得最短路径问题（ESPO） 472
9.4.3求解E3中ESPO问题的算法 474
9.4.4具有障碍物的Steiner最小树问题（ESMTO） 486
第10章 随机几何算法与并行几何算法 491
10.1分类和搜索线性表的随机算法 492
10.1.1随机二叉树 493
10.1.2跳越表 496
10.2增量算法 498
10.2.1四边形分解 498
10.2.2凸多胞形 502
10.2.3 Voronoi图 506
10.2.4构形空间 508
10.3动态算法 511
10.4随机抽样 515
10.4.1具有限界的构形空间 516
10.4.2顶-向下的抽样 517
10.4.3底-向上的抽样 519
10.4.4动态抽样 521
10.5并行几何算法 523
10.5.1凸壳问题 527
10.5.2排列与分解 528
10.5.3邻近 530
10.5.4几何搜索 530
10.5.5可视性和最优化 531
待解决的问题 533
算法一览 535
参考文献 541
名词索引 555