（已有13条评价）基本信息
- 作者： 周培德
- 丛书名： 中国计算机学会学术著作丛书
- 出版社：清华大学出版社
- ISBN：7302101965
- 上架时间：2005-4-27
- 出版日期：2005 年4月
- 开本：175×245
- 页码：433
- 版次：2-1
- 所属分类：计算机 > 计算机科学理论与基础知识 > 计算理论 > 算法
内容简介
作译者
周培德 1941年生，湖北省武穴市人。1965年毕业于武汉大学数学系；任北京理工大学计算机系教授。2001年9月退休。
长期担任本科生“算法设计与分析”及研究生“计算理论”等课程的教学工作。主要精力集中于计算机算法设计与分析、计算几何等方面的研究。以个人名义在多种学术刊物和全国学术交流会上发表论文60余篇，出版学术专著一部、全国统编高等学校教材一部、校“九五”规划研究生教材一部、内部教材八部。主要论著有《计算几何——算法分析与设计(第一版)》、《算法设计与分析》、《计算中的基本理沦与方法》。代表性论文有《求解k-中心问题的快速算法》、《平面散乱点线集三角剖分的算法》、《平面线段集三角剖分的算法》、《连接不相交线段成简单多边形(链)的算法》、《确定任意多边形凸凹顶点的算法》、《货郎担问题的几何解法》、《平面点集三角剖分的算法》、《连接两个多边形成一条回路的算法》、《分割多边形成凸多边形的算法》等。《算法设计与分析》一书获第三届全国普通高校部级优秀教材一等奖，《平面点集三角剖分的算法》等论文被EI、MR检索。
退休三年来，专心从事计算几何及其应用领域的研究工作，为6个课题组、公司设计了20余个算法，在多种期刊上发表学术论文20余篇，提出一批新的问题及解决相应问题的算法。
长期担任本科生“算法设计与分析”及研究生“计算理论”等课程的教学工作。主要精力集中于计算机算法设计与分析、计算几何等方面的研究。以个人名义在多种学术刊物和全国学术交流会上发表论文60余篇，出版学术专著一部、全国统编高等学校教材一部、校“九五”规划研究生教材一部、内部教材八部。主要论著有《计算几何——算法分析与设计(第一版)》、《算法设计与分析》、《计算中的基本理沦与方法》。代表性论文有《求解k-中心问题的快速算法》、《平面散乱点线集三角剖分的算法》、《平面线段集三角剖分的算法》、《连接不相交线段成简单多边形(链)的算法》、《确定任意多边形凸凹顶点的算法》、《货郎担问题的几何解法》、《平面点集三角剖分的算法》、《连接两个多边形成一条回路的算法》、《分割多边形成凸多边形的算法》等。《算法设计与分析》一书获第三届全国普通高校部级优秀教材一等奖，《平面点集三角剖分的算法》等论文被EI、MR检索。
退休三年来，专心从事计算几何及其应用领域的研究工作，为6个课题组、公司设计了20余个算法，在多种期刊上发表学术论文20余篇，提出一批新的问题及解决相应问题的算法。
目录
第2版前言Ⅴ
第1版前言Ⅶ
第0章预备知识1
0.1算法与数据结构2
0.1.1算法2
0.1.2数据结构5
0.2相关的几何知识9
0.2.1基本定义9
0.2.2线性变换群下的不变量11
0.2.3几何对偶性12
0.3计算模型13
第1章几何查找(检索)17
1.1点定位问题18
1.1.1点q是否在多边形P内19
1.1.2确定点q在平面剖分中的位置24
1.1.3Z1-3算法30
1.2范围查找问题31
1.2.1多维二叉树(kD树)的方法32
1.2.2直接存取方法34
1.2.3范围树方法36
第1版前言Ⅶ
第0章预备知识1
0.1算法与数据结构2
0.1.1算法2
0.1.2数据结构5
0.2相关的几何知识9
0.2.1基本定义9
0.2.2线性变换群下的不变量11
0.2.3几何对偶性12
0.3计算模型13
第1章几何查找(检索)17
1.1点定位问题18
1.1.1点q是否在多边形P内19
1.1.2确定点q在平面剖分中的位置24
1.1.3Z1-3算法30
1.2范围查找问题31
1.2.1多维二叉树(kD树)的方法32
1.2.2直接存取方法34
1.2.3范围树方法36
前言
第2版前言
第2版对第1版的补充与修改如下：新增26节(1．1．3，1．4，2．5，2．6，2．7，2．8，2．9，2．10，2．11，2．12，3．3，3．4，3．5，4．4，4．5，4．6．9，4．6．11，4．6．12，4．6．13，5．6，8．1．2，8．1．3，8．1．4，8．7，9．1．3，9．1．4)，删去3节，修改10节。新增的内容都是作者最近三年内的研究成果(49个算法，使作者设计的Z算法增至88个，占全书算法总数62％)。
这里需要再次强调，为了给读者留下一定的思考余地，书中新增加的某些Z算法仍然是以基本形式出现的。
作者才疏学浅，新增内容错误在所难免，敬请同行与读者批评指正。
周培德
2004年9月
Email：zhou_pd@sina．com
http：／／www．china biz 114．com／zhoupd．htm
第1版前言
1975年，Shamos(沙莫斯)和Hoey(霍伊)利用计算机有效地计算平面点集的Voronoi图，并发表了一篇著名论文，从此计算几何诞生了。自那时以来该研究领域取得了辉煌的成果，使得计算几何成为理论计算机科学领域中一个新的极有生命力的子领域，并且，计算几何中的研究成果已在计算机图形学、化学、统计分析、模式识别、地理数据库以及其他许多领域中得到了广泛的应用。
计算几何研究的典型问题由几何基元(geometric primitives)、查找、优化等问题类组成。
首先，几何基元包括凸壳和Voronoi图、多边形的三角剖分、划分问题(partition problems)与相交问题。Ed+1中点集S的下凸壳在Ed中的投影恰好是点集S在Ed中投影点的Delaunoy三角剖分，然后由Delounay三角剖分可以容易地得到Voronoi图。换言之，Voronoi图是凸壳的特例，因此构造Ed+1中点集凸壳的算法也可以用于构造Ed中点集的Voronoi图。对多边形的三角剖分问题可以提出如下要求：设计复杂度低的算法构造多边形三角剖分以及设计三角形最小角最大化的三角剖分算法；分割线段长度之和最小的三角剖分算法。前者已有线性时间的算法。划分问题是多边形三角剖分的推广，它要求把几何体划分成若干好的部分。所谓好的部分通常是指下述两个目标之一：划分成尽量少的凸部分；各凸部分最小角最大化。另外，在几何体中可以加入Steiner点(新的顶点)，然后再进行划分，使得划分线段长度之和最小化或者提出其他要求。二维中的典型相交问题是：给定平面上n条直线段，确定所有的相交线对。三维中的相交问题一般考虑两个凸多面体的交以及两个多面体的交。
其次，几何查找包括点定位、可视化、区域查找等问题。计算机图形学、数据库中的区域查找及地理图形中的点定位等都是几何查找中的典型例子。在平面细分(planar subdivision)中定位一个询问点或者在Ed(d≥3)内由72个超平面构成的结构中定位询问点的问题是一个典型问题，现在不仅有解决这个问题的确定型算法，而且设计了动态随机增量算法。给定平面上n个顶点的简单多边形P，由点q向任一方向引射线l，确定l与P相交的第一条边，这个问题的解决为可视化问题的求解提供了前提。Ed中给定点集S及区域集合B，b∈B，要求在b中查找S中的点，这是区域查找问题。
再次，几何优化包括参数查找和线性规划。参数查找技术是将一个优化问题的检验算法变成寻找解的算法，它必须满足某些条件(检验算法是可以并行的)，并且具有广泛的应用性。例如，可用它来求解平面中2-中心问题，还可以用来完成三维空间中射线的安置。众所周知，有确定变元数目的线性规划问题已有线性时间算法求解，但对于广义线性规划是否存在多项式时间算法还有待进一步研究。
此外，计算几何中各种问题的下界的确定、推导下界的方法以及求解各种几何问题的算法的复杂性分析等，也是计算几何研究的重要内容。
计算几何中引入随机化之后，已经设计出非常有效的概率算法求解诸多几何问题。随机化给几何算法设计带来两种新的设计思想：基于随机抽样的分治方法；利用随机顺序插入产生随机增量结构。此外，随机几何算法的复杂性分析以及随机增量结构的非随机化也是重要的研究内容。
计算几何的新近发展包括几何抽样理论、计算实代数几何、计算拓扑、运动规划、并行计算几何、隐藏面的移动、结构和图形、网络生成以及计算机视觉中的几何问题等。计算机在各学科领域深层次的应用将为计算几何提出更多的研究问题，反之，计算几何的研究成果也将促进这些学科的进一步发展。
本书是以上述部分问题的前人研究成果与作者在本领域中所做的工作为基础撰写而成的。书中主要叙述解决某些几何问题的算法并兼顾复杂性分析。书中较详细地陈述了98个算法，其中39个算法是作者提出的，并编号为Z1-1算法至Z10-2算法。书中的某些Z算法是以基本形式出现的，对这些算法可以进行修改并降低复杂性的阶或扩充应用范围，而且实现这些算法的某些步骤需要一些技巧。
全书共分11章。第0章是预备知识。第1章介绍几何查找，包括点和点集的定位、范围查找与平面网络的处理。第2章叙述多边形与多边形的划分及相关问题。第3、4、7章分别介绍计算几何中的三个基本结构：凸壳、Voronoi图与几何体的排列。第5章阐述线段、多边形、半平面、凸多面体的交，多边形的并及应用。第6章介绍矩形几何。第8章叙述算法的运动规划，所讨论的问题源于机器人学。第9章的中心论题是几何拓扑网络设计，其内容具有广泛的实用性。第?o章介绍随机几何算法和并行几何算法。
描述算法有诸多形式。为了便于理解算法又不至于产生二义性，而且利于编制上机程序，本书描述算法就不拘泥于某一种形式，但以步骤、拟ALGOL语言、中文语句、数学表达式及逻辑运算符等相结合的描述形式为主。另外，本书以处于一般位置的几何体为讨论对象。对于退化情况，则另行处理。
第2版对第1版的补充与修改如下：新增26节(1．1．3，1．4，2．5，2．6，2．7，2．8，2．9，2．10，2．11，2．12，3．3，3．4，3．5，4．4，4．5，4．6．9，4．6．11，4．6．12，4．6．13，5．6，8．1．2，8．1．3，8．1．4，8．7，9．1．3，9．1．4)，删去3节，修改10节。新增的内容都是作者最近三年内的研究成果(49个算法，使作者设计的Z算法增至88个，占全书算法总数62％)。
这里需要再次强调，为了给读者留下一定的思考余地，书中新增加的某些Z算法仍然是以基本形式出现的。
作者才疏学浅，新增内容错误在所难免，敬请同行与读者批评指正。
周培德
2004年9月
Email：zhou_pd@sina．com
http：／／www．china biz 114．com／zhoupd．htm
第1版前言
1975年，Shamos(沙莫斯)和Hoey(霍伊)利用计算机有效地计算平面点集的Voronoi图，并发表了一篇著名论文，从此计算几何诞生了。自那时以来该研究领域取得了辉煌的成果，使得计算几何成为理论计算机科学领域中一个新的极有生命力的子领域，并且，计算几何中的研究成果已在计算机图形学、化学、统计分析、模式识别、地理数据库以及其他许多领域中得到了广泛的应用。
计算几何研究的典型问题由几何基元(geometric primitives)、查找、优化等问题类组成。
首先，几何基元包括凸壳和Voronoi图、多边形的三角剖分、划分问题(partition problems)与相交问题。Ed+1中点集S的下凸壳在Ed中的投影恰好是点集S在Ed中投影点的Delaunoy三角剖分，然后由Delounay三角剖分可以容易地得到Voronoi图。换言之，Voronoi图是凸壳的特例，因此构造Ed+1中点集凸壳的算法也可以用于构造Ed中点集的Voronoi图。对多边形的三角剖分问题可以提出如下要求：设计复杂度低的算法构造多边形三角剖分以及设计三角形最小角最大化的三角剖分算法；分割线段长度之和最小的三角剖分算法。前者已有线性时间的算法。划分问题是多边形三角剖分的推广，它要求把几何体划分成若干好的部分。所谓好的部分通常是指下述两个目标之一：划分成尽量少的凸部分；各凸部分最小角最大化。另外，在几何体中可以加入Steiner点(新的顶点)，然后再进行划分，使得划分线段长度之和最小化或者提出其他要求。二维中的典型相交问题是：给定平面上n条直线段，确定所有的相交线对。三维中的相交问题一般考虑两个凸多面体的交以及两个多面体的交。
其次，几何查找包括点定位、可视化、区域查找等问题。计算机图形学、数据库中的区域查找及地理图形中的点定位等都是几何查找中的典型例子。在平面细分(planar subdivision)中定位一个询问点或者在Ed(d≥3)内由72个超平面构成的结构中定位询问点的问题是一个典型问题，现在不仅有解决这个问题的确定型算法，而且设计了动态随机增量算法。给定平面上n个顶点的简单多边形P，由点q向任一方向引射线l，确定l与P相交的第一条边，这个问题的解决为可视化问题的求解提供了前提。Ed中给定点集S及区域集合B，b∈B，要求在b中查找S中的点，这是区域查找问题。
再次，几何优化包括参数查找和线性规划。参数查找技术是将一个优化问题的检验算法变成寻找解的算法，它必须满足某些条件(检验算法是可以并行的)，并且具有广泛的应用性。例如，可用它来求解平面中2-中心问题，还可以用来完成三维空间中射线的安置。众所周知，有确定变元数目的线性规划问题已有线性时间算法求解，但对于广义线性规划是否存在多项式时间算法还有待进一步研究。
此外，计算几何中各种问题的下界的确定、推导下界的方法以及求解各种几何问题的算法的复杂性分析等，也是计算几何研究的重要内容。
计算几何中引入随机化之后，已经设计出非常有效的概率算法求解诸多几何问题。随机化给几何算法设计带来两种新的设计思想：基于随机抽样的分治方法；利用随机顺序插入产生随机增量结构。此外，随机几何算法的复杂性分析以及随机增量结构的非随机化也是重要的研究内容。
计算几何的新近发展包括几何抽样理论、计算实代数几何、计算拓扑、运动规划、并行计算几何、隐藏面的移动、结构和图形、网络生成以及计算机视觉中的几何问题等。计算机在各学科领域深层次的应用将为计算几何提出更多的研究问题，反之，计算几何的研究成果也将促进这些学科的进一步发展。
本书是以上述部分问题的前人研究成果与作者在本领域中所做的工作为基础撰写而成的。书中主要叙述解决某些几何问题的算法并兼顾复杂性分析。书中较详细地陈述了98个算法，其中39个算法是作者提出的，并编号为Z1-1算法至Z10-2算法。书中的某些Z算法是以基本形式出现的，对这些算法可以进行修改并降低复杂性的阶或扩充应用范围，而且实现这些算法的某些步骤需要一些技巧。
全书共分11章。第0章是预备知识。第1章介绍几何查找，包括点和点集的定位、范围查找与平面网络的处理。第2章叙述多边形与多边形的划分及相关问题。第3、4、7章分别介绍计算几何中的三个基本结构：凸壳、Voronoi图与几何体的排列。第5章阐述线段、多边形、半平面、凸多面体的交，多边形的并及应用。第6章介绍矩形几何。第8章叙述算法的运动规划，所讨论的问题源于机器人学。第9章的中心论题是几何拓扑网络设计，其内容具有广泛的实用性。第?o章介绍随机几何算法和并行几何算法。
描述算法有诸多形式。为了便于理解算法又不至于产生二义性，而且利于编制上机程序，本书描述算法就不拘泥于某一种形式，但以步骤、拟ALGOL语言、中文语句、数学表达式及逻辑运算符等相结合的描述形式为主。另外，本书以处于一般位置的几何体为讨论对象。对于退化情况，则另行处理。
序言
第一台电子计算机诞生于20世纪40年代。到目前为止，计算机的发展已远远超出了其创始者的想象。计算机的处理能力越来越强，应用面越来越广，应用领域也从单纯的科学计算渗透到社会生活的方方面面： 从工业、国防、医疗、教育、娱乐直至人们的日常生活，计算机的影响可谓无处不在。
计算机之所以能取得上述地位并成为全球最具活力的产业，原因在于其高速的计算能力、庞大的存储能力以及友好灵活的用户界面。而这些新技术及其应用有赖研究人员多年不懈的努力。学术研究是应用研究的基础，也是技术发展的动力。
自1992年起，清华大学出版社与广西科学技术出版社为促进我国计算机科学技术与产业的发展，推动计算机科技著作的出版，设立了“计算机学术著作出版基金”，并将资助出版的著作列为中国计算机学会的学术著作丛书。时至今日，本套丛书已出版学术专著近50种，产生了很好的社会影响，有的专著具有很高的学术水平，有的则奠定了一类学术研究的基础。中国计算机学会一直将学术著作的出版作为学会的一项主要工作。本届理事会将秉承这一传统， 继续大力支持本套丛书的出版， 鼓励科技工作者写出更多的优秀学术著作，多出好书，多出精品， 为提高我国的知识创新和技术创新能力，促进计算机科学技术的发展和进步做出更大的贡献。
中国计算机学会
2002年6月14日
计算机之所以能取得上述地位并成为全球最具活力的产业，原因在于其高速的计算能力、庞大的存储能力以及友好灵活的用户界面。而这些新技术及其应用有赖研究人员多年不懈的努力。学术研究是应用研究的基础，也是技术发展的动力。
自1992年起，清华大学出版社与广西科学技术出版社为促进我国计算机科学技术与产业的发展，推动计算机科技著作的出版，设立了“计算机学术著作出版基金”，并将资助出版的著作列为中国计算机学会的学术著作丛书。时至今日，本套丛书已出版学术专著近50种，产生了很好的社会影响，有的专著具有很高的学术水平，有的则奠定了一类学术研究的基础。中国计算机学会一直将学术著作的出版作为学会的一项主要工作。本届理事会将秉承这一传统， 继续大力支持本套丛书的出版， 鼓励科技工作者写出更多的优秀学术著作，多出好书，多出精品， 为提高我国的知识创新和技术创新能力，促进计算机科学技术的发展和进步做出更大的贡献。
中国计算机学会
2002年6月14日
