计算几何

出版时间：2008-7  出版社：清华大学出版社  作者：周培德  页数：560  
Tag标签：无  

内容概要

　　本书系统地介绍了计算几何中的基本概念、求解诸多问题的算法及复杂性分析，概括了求解几何问题所特有的许多思想方法、几何结构与数据结构。全书共分11章，包括：预备知识，几何查找（检索），多边形，凸壳及其应用，Voronoi图、三角剖分及其应用，交与并及其应用，多边形的获取及相关问题，几何体的划分与等分、算法的运动规划、几何拓扑网络设计、随机几何算法与并行几何算法等。　　本书可作为高等院校计算机专业研究生或本科高年级学生的教材，也可作为相关专业科技工作者的参考书。

作者简介

　　周培德，1941年，湖北省武穴市人。1965年毕业于武汉大学数学系。任北京理工大学计算机系教授。
　　主要成果为：个人独立发明计算机算法160多个，发表学术论文60余篇，出版学术专著3部，研究生教材两部。

书籍目录

第0章  预备知识  0.1  算法与数据结构    0.1.1  算法    0.1.2  数据结构  0.2  相关的几何知识    0.2.1  基本定义    0.2.2  线性变换群下的不变量    0.2.3  几何对偶性  0.3  计算模型第1章  几何查找（检索）  1.1点  定位问题    1.1.1  点q是否在多边形P内    1.1.2  确定点q在平面剖分中的位置    1.1.3  Z1-3算法（判定点q在哪个三角形的算法）  1.2  范围查找问题    1.2.1  多维二叉树（k-D树）的方法    1.2.2  直接存取方法    1.2.3  范围树方法  1.3  判定点集是否在多边形内  1.4  平面网络的处理与点q的定位  1.5  平面上链的处理与点q的定位  1.6  平面上线段的处理与点q的定位第2章  多边形  2.1  凸多边形  2.2  简单多边形  2.3  多边形的三角剖分  2.4  多边形的凸划分第3章  凸壳及其应用  3.1　凸壳的基本概念  ……第4章  Voronoi图、三角剖分及其应用第5章  交与并及其应用第6章  多边形的获取及相关问题第7章  几何体的划分与等分第8章  算法的运动规划第9章  几何拓扑网络设计第10章  随机几何算法与并行几何算法待解决的问题算法一览参考文献名词索引

章节摘录

第0章　预备知识0.1　算法与数据结构0.1.1 算法众所周知，算法是求解一个问题类的无二义性的有穷过程。这里的过程是指求解问题执行的一步一步动作的集合，每一步动作只需要有限的存储单元和有限的操作时间。另外，如果详细说明一台典型的计算机以及与这种计算机通信的语言，那么凡用这种语言编写的、可以在给定的计算机上执行的过程便称为算法。随机存取机器（RAM）、图灵机等可以作为典型的计算机，拟ALGOL语言作为描述算法而非执行的语言。应该指出，算法不等于程序，因此描述算法的方式将是多种形式的，如在拟ALGOL语言的描述中可以使用数学记号和自然语言。为了把算法转换成上机程序，还需要进行编程工作。算法的复杂性包括算法的时间复杂性和算法的空间复杂性。为了说明复杂性的概念，先介绍问题规模的概念。用一个与问题相关的整数量来衡量问题的大小，该整数量表示输入数据量的尺度，称为问题的规模。比如，行列式的规模可以用其阶数n来表示，图问题的规模可以用其边数或顶点数来表示，等等。利用某算法处理一个问题规模为n的输入所需要的时间，称为该算法的时间复杂性。它显然是n的函数，记为T（n）。类似地，可以定义算法的空间复杂性S（n）。下面主要讨论算法的时间复杂性。由于一般不需要知道精确的时间耗费，只要知道时间耗费的增长率大体在什么范围内即可，因此我们引入算法复杂性阶的概念。

编辑推荐

《计算几何:算法设计与分析(第3版)》可作为高等院校计算机专业研究生或本科高年级学生的教材，也可作为相关专业科技工作者的参考书。

用户评论 (总计18条)

•   计算机图形学要用到，所以买下来。。挺深的，以后会派上用场~！！
•   分析过程详细，代码有注释，是一个难得的acm教材，顶！
•   很好这本书，讲的非常的详细
•   是正版，价格还便宜，货到付款，非常不错
•   东西很好，快递也很快，不错。
•   了解计算几何的研究方法
•   内容相当专业，消化他得要一段时间......................................................................................
•   比较经典的参考书
•   这本书质量很好，和正版的一模一样
•   不错的书。阅读中~~~
•   内容比较深，但是理论上讲的还是比较清楚的。
•   收藏起来，有空在说
•   太专业了，很多在讲他自己提出的算法，又都是伪码，学术研究和大项目的应用恐怕还有点用，如果初学计算几何，貌似不怎么看得懂，没法根据那个直接写出可以处理简单问题的程序。
•   稍微有点难以看懂，不过如果你是搞研究的，应该是比较有用的。
•   感觉内容很多，但是很乱，有些符号没解释清楚，原理也分析的不够，虽然算法很多。
•   比第二版在内容上有所充实，作为一般算法参考书，还是可以借鉴的。
•   我正在编写有关程序，该书所叙述的算法正合我用。要是能用C++语言来描述算法就更好了，当然，现在这样也可以，我能够把它写成C++。谢谢作者。
•   书的内容比较详细，但是没有可执行的代码，只有伪码实现