计算几何导论PDF电子书下载

第一章 引言 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 分治算法 1 38

2.1 几何查找的引言 45

第二章 几何查找 45

2.2 点定位问题 50

2.2.1 一般考虑．简单情形 50

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

4.1.1 平均情形分析 1 83

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