《计算几何导论》求取 ⇩

第一章引言1

1.1 历史透视1

1.1.1 古典几何学中的复杂性概念3

1.1.2 凸集，度量几何和组合几何的理论5

1.1.3 先前有关的研究工作6

1.1.4 关于计算几何6

1.2 算法的基础知识7

1.2.1 算法：它们的表示和性能估计8

1.2.2 关于一般算法技巧的一些考虑12

1.2.3 数据结构13

1.3 几何的准备工作21

1.3.1 一般定义和记法21

1.3.2 线性变换群之下的不变量24

1.3.3 几何对偶性．配极变换29

1.4 计算的模型33

3.3.5 分治算法 138

2.1 几何查找的引言45

第二章几何查找45

2.2 点定位问题50

2.2.1 一般考虑．简单情形50

2.2.2 在平面剖分中一点的定位56

4.1.1 平均情形分析 183

2.3 范围查找问题85

2.3.1 一般考虑85

2.3.2 多维二叉树（k-D树）的方法91

2.3.3 直接存取方法和它的变形98

2.3.4 范围树方法和它的变形103

2.4 评论和注解108

2.5 习题112

第三章凸壳：基本算法113

3.1 准备工作114

3.2 问题陈述和下界118

3.3 平面中的凸壳算法124

3.3.1 最初建立的一个凸壳算法124

3.3.2 Graham的扫描128

3.3.3 Jarvi？的行进132

3.3.4 快速凸壳（QUICKHULL）技巧134

3.3.6 动态凸壳算法142

3.3.7 一个推广：动态凸壳的维持150

3.4 高于二维中的凸壳158

3.4.1 礼品包扎方法159

3.4.2 以下-以上的方法166

3.4.3 三维中的凸壳171

3.5 评论和注解178

3.6 习题181

4.1 扩展和变形183

第四章凸壳：扩展和应用183

4.1.2 凸壳的近似算法187

4.1.3 一个点集的最大问题192

4.1.4 一个简单多边形的凸壳203

4.2 统计的应用209

4.2.1 强估计210

4.2.2 保序回归213

4.2.3 聚集（点集的直径）215

4.3 评论和注解223

4.4 习题224

第五章邻近问题：基本算法226

5.1 一组问题227

5.2 一个计算原型：元素唯一性233

5.3 下界235

5.4 最接近的点对问题：一种分治法238

5.5 邻近问题的轨迹方法：Voronoi图250

5.5.1 Voronoi图性质的一览表252

5.5.2 构造Voronoi图259

5.6 用Voronoi图解邻近问题271

5.7 评论和注解273

5.8 习题276

第六章邻近问题：变形和推广278

6.1 欧几里得最小生成树278

6.1.1 欧几里得流动售货员284

6.2 平面三角剖分288

6.2.1 贪婪三角剖分289

6.2.2 限定的三角剖分292

6.3 Voronoi图的推广297

6.3.1 （平面中的）高阶Voronoi图298

6.3.2 多维最接近点Voronoi图和最远点Voronoi图313

6.4 空隙和覆盖316

6.5 评论和注解323

6.6 习题327

第七章交330

7.1 应用的实例331

7.1.1 隐藏线和隐藏面问题331

7.1.2 模式识别332

7.1.3 导线和元件布局334

7.1.4 线性规划和半空间的公共交335

7.2.1 凸多边形的交336

7.2 平面应用336

7.2.2 星形多边形的交344

7.2.3 线段的交345

7.2.4 半平面的交357

7.2.5 两个变量的线性规划360

7.2.6 一个平面多边形的核372

7.3 三维应用381

7.3.1 凸多面体的交381

7.3.2 半空间的交392

7.4 评论和注解398

7.5 习题402

第八章矩形几何404

8.1 矩形几何的几个应用404

8.1.1 超大规模集成电路的辅助设计404

8.1.2 数据库中的并发控制406

8.2 结论有效的范围410

8.3 关于静态方式算法的一般研究412

8.4 矩形并的度量和周长414

8.5 矩形并的轮廓425

8.6 矩形并的闭包435

8.7 矩形并的外轮廓441

8.8 矩形的交和有关问题447

8.8.1 矩形的交448

8.8.2 回到矩形交问题453

8.8.3 矩形的包围456

8.9 评论和注解464

8.10 习题466

参考文献467

索引478