前言 I
1 ?计算几何：导言 1
1.1 凸包的例子 2
1.2 退化及鲁棒性 9
1.3 应用领域 10
1.3.1 计算机图形学 10
1.3.2 机器人学 11
1.3.3 地理信息系统 11
1.3.4 CAD/CAM 12
1.3.5 其他应用领域 12
1.4 注释及评论 13
习题 15
2 ?线段求交：专题图叠合 19
2.1 线段求交 20
2.2 双向链接边表 30
2.3 计算子区域划分的叠合 34
2.4 布尔运算 41
2.5 注释及评论 42
习题 43
3 ?多边形三角剖分：画廊看守 47
3.1 看守与三角剖分 48
3.2 多边形的单调块划分 52
3.3 单调多边形的三角剖分 59
3.4 注释及评论 63
习题 64
4 ?线性规划：铸模制造 67
4.1 铸造中的几何 68
4.2 半平面求交 70
4.3 递增式线性规划 75
4.4 随机线性规划 81
4.5 无界线性规划问题 84
4.6* 高维空间中的线性规划 87
4.7* 最小包围圆 91
4.8 注释及评论 95
习题 96
5 ?正交区域查找：数据库查询 99
5.1 一维区域查找 100
5.2 kd-树 103
5.3 区域树 109
5.4 高维区域树 113
5.5 一般性点集 115
5.6* 分散层叠 116
5.7 注释及评论 119
习题 121
6 ?点定位：找到自己的位置 125
6.1 点定位及梯形图 126
6.2 随机增量式算法 132
6.3 退化情况的处理 141
6.4* 尾分析 143
6.5 注释及评论 147
习题 148
7 ? Voronoi图：邮局问题 151
7.1 定义及基本性质 152
7.2 构造Voronoi图 156
7.3 线段集Voronoi图 165
7.4 最远点Voronoi图 169
7.5 注释及评论 173
习题 175
8 ?排列与对偶：光线跟踪超采样 179
8.1 差异值的计算 181
8.2 对偶变换 183
8.3 直线的排列 186
8.4 层阶与偏差 192
8.5 注释及评论 193
习题 195
9 ? Delaunay三角剖分：高度插值 197
9.1 平面点集的三角剖分 199
9.2 Delaunay三角剖分 202
9.3 构造Delaunay三角剖分 206
9.4 分析 211
9.5* 随机算法框架 215
9.5.1 半平面求交 216
9.5.2 梯形图 216
9.5.3 Delaunay三角剖分 216
9.6 注释及评论 220
习题 221
10 ?更多几何数据结构：截窗 225
10.1 区间树 226
10.2 优先查找树 232
10.3 线段树 236
10.4 注释及评论 243
习题 244
11 ?凸包：混合物 249
11.1 三维凸包的复杂度 251
11.2 构造三维凸包 252
11.3* 分析 256
11.4* 凸包与半空间求交 259
11.5* 再论Voronoi图 261
11.6 注释及评论 263
习题 264
12 ?空间二分：画家算法 267
12.1 BSP树的定义 269
12.2 BSP树及画家算法 270
12.3 构造BSP树 272
12.4* 三维BSP树的规模 276
12.5 低密度场景的BSP树 279
12.6 注释及评论 286
习题 288
13 ?机器人运动规划：随意所之 291
13.1 工作空间与C-空间 292
13.2 点机器人 295
13.3 Minkowski和 299
13.4 平移式运动规划 306
13.5* 允许旋转的运动规划 308
13.6 注释及评论 311
习题 313
14 ?四叉树：非均匀网格生成 315
14.1 均匀及非均匀网格 316
14.2 点集的四叉树 318
14.3 从四叉树到网格 324
14.4 注释及评论 327
习题 328
15 ?可见性图：求最短路径 331
15.1 点机器人的最短路径 332
15.2 构造可见性图 335
15.3 平移运动多边形机器人的最短路径 339
15.4 注释及评论 339
习题 341
16 ?单纯形区域查找：再论截窗 343
16.1 划分树 344
16.2 多层划分树 350
16.3 切分树 353
16.4 注释及评论 358
习题 360
参考文献 363
图表索引 385
观察结论、引理、定理及推论索引 393
关键词索引 397
