第1章计算几何：导言

1.1凸包的例子

1.2退化及稳健性

1.3应用领域

1.4注释及评论

1.5习题

第2章线段求交：专题图叠合

2.1线段求交

2.2双向链接边表

2.3计算子区域划分的叠合

2.4布尔运算

2.5注释及评论

2.6习题

第3章多边形三角剖分：画廊看守

3.1覆盖与三角剖分

3.2多边形的单调块划分

3.3单调多边形的三角剖分

3.4注释及评论

3.5习题

第4章线性规划：铸模制造

4.1铸造中的几何

4.2半平面求交

4.3递增式线性规划

4.4随机线性规划

4.5无界线性规划问题

*4.6高维空间中的线性规划

*4.7最小包围圆

4.8注释及评论

4.9习题

第5章正交区域查找：数据库查询

5.1一维区域查找

5.2kd树

5.3区域树

5.4高维区域树

5.5一般性点集

*5.6分散层叠

5.7注释及评论

5.8习题

第6章点定位：找到自己的位置

6.1点定位及梯形图

6.2随机增量式算法

6.3退化情况的处理

*6.4尾分析

6.5注释及评论

6.6习题

第7章Voronoi图：邮局问题

7.1定义及基本性质

7.2构造Voronoi图

7.3注释及评论

7.4习题

第8章排列与对偶：光线跟踪超采样

8.1差异值的计算

8.2对偶变换

8.3直线的排列

8.4层阶与偏差

8.5注释及评论

8.6习题

第9章Delaunay三角剖分：高度插值

9.1平面点集的三角剖分

9.2Delaunay三角剖分

9.3构造Delaunay三角剖分

9.4分析

*9.5随机算法框架

9.6注释及评论

9.7习题

第10章更多几何数据结构：截窗

10.1区间树

10.2优先查找树

10.3线段树

10.4注释及评论

10.5习题

第11章凸包： 混合物

11.1三维凸包的复杂度

11.2构造三维凸包

*11.3分析

*11.4凸包与半空间求交

*11.5再论Voronoi图

11.6注释及评论

11.7习题

第12章空间二分：画家算法

12.1BSP树的定义

12.2BSP树及画家算法

12.3构造BSP树

*12.4三维BSP树的规模

12.5注释及评论

12.6习题

第13章机器人运动规划：随意所之

13.1工作空间与C空间

13.2点机器人

13.3Minkowski和

13.4平移式运动规划

*13.5允许旋转的运动规划

13.6注释及评论

13.7习题

第14章四叉树：非均匀网格生成

14.1均匀及非均匀网格

14.2点集的四叉树

14.3从四叉树到网格

14.4注释及评论

14.5习题

第15章可见性图：求最短路径

15.1点机器人的最短路径

15.2构造可见性图

15.3平移运动多边形机器人的最短路径

15.4注释及评论

15.5习题

第16章单纯形区域查找：再论截窗

16.1划分树

16.2多层划分树

16.3切分树

16.4注释及评论

16.5习题

参考文献

关键词索引