计算几何是计算机理论科学的一个重要分支.自20世纪70年代末从算法设计与分析中独立出来起，不到30年，该学科已经有了巨大的发展，不仅产生了一系列重要的理论成果，也在众多实际领域中得到了广泛的应用. 本书的前4章对几何算法进行了讨论，包括几何求交、三角剖分、线性规划等，其中涉及的随机算法也是本书的一个鲜明特点.第5章至第10章介绍了多种几何结构，包括几何查找、kd树、区域树、梯形图、Voronoi图、排列、Delaunay三角剖分、区间树、优先查找树以及线段树等.第11章至第16章结合实际问题，继续讨论了若干几何算法及其数据结构，包括高维凸包、空间二分及BSP树、运动规划、网格生成及四叉树、最短路径查找及可见性图、单纯性区域查找及划分树和切分树等，这些也是对前十章内容的进一步深化. 本书不仅内容全面，而且紧扣实际应用，重点突出，既有深入的讲解，同时每章都设有“注释及评论”和“习题”，为读者更深入的理解提供了可能.因此近年来作为教材一直流行于世界众多大学校园中.我国在计算几何方面的研究起步较晚，相信本书的出版能对国内此方面教学工作的开展有所推动.

20世纪70年代末，计算几何从算法设计与分析中孕育而生.今天，它不仅拥有自己的学术刊物和学术会议，而且形成了一个由众多活跃的研究人员组成的学术群体，因此已经成长为一个被广泛认同的学科.该领域作为一个研究学科之所以会取得成功，一方面是由于其涉及的问题及其解答本身所具有的美感，另一方面，也是由于在众多的应用领域（诸如计算机图形学、地理信息系统和机器人学等）中，几何算法都发挥了重要的作用. 解决许多几何问题的早期算法，要么速度很慢，要么难以理解与实现.随着近年来一些新的算法技术的发展，此前的很多方法都得到了改进与简化.在这本教材中，我们力图使这些现代的算法能够被更广泛的读者理解和接受.本书既是面向计算几何课程的一本教材，同时也可用于自学. 本书的结构.除“导言”外，每一章都从来自应用领域的某一实际问题入手，这个问题将被转化为一个纯粹的几何问题，并通过计算几何所提供的方法得到解决.每一章所讨论的，实质上就是对应的几何问题，以及解决该问题所需要的概念与方法.我们根据所希望覆盖的计算几何专题，来选取有关的应用；而就具体的应用领域而言，这些介绍还远远不够全面.引入这些应用的目的，只是为了激发读者的兴趣；而各章本身的目的，并不在于为这些问题提供现成可用的解决方法.虽然如此，我们还是认为，为了有效地解决应用中的几何问题，计算几何方面的知识是非常重要的.我们希望本书不仅能够吸引从事算法研究的学者，而且对应用领域的读者也同样有所帮助. 同一几何问题，可能有多种不同的解决方法，不过，在论述大多数几何问题时，我们将只给出其中一种.我们通常所选取的，都是最易于理解与实...