清华大学出版社

20世纪70年代末，计算几何学（computational geometry）从算法设计与分析中孕育而生。今天，它不仅拥有自己的学术刊物和学术会议，而且形成了一个由众多活跃的研究人员组成的学术群体，因此已经成长为一个被广泛认同的学科。该领域作为一个研究学科之所以会取得成功，一方面是由于其涉及的问题及其解答本身所具有的美感，而另一方面，也是由于在（诸如计算机图形学、地理信息系统和机器人学等）众多的应用领域中，几何算法都发挥了重要的作用。

20世纪70年代末，计算几何学（computational geometry）从算法设计与分析中孕育而生。今天，它不仅拥有自己的学术刊物和学术会议，而且形成了一个由众多活跃的研究人员组成的学术群体，因此已经成长为一个被广泛认同的学科。该领域作为一个研究学科之所以会取得成功，一方面是由于其涉及的问题及其解答本身所具有的美感，而另一方面，也是由于在（诸如计算机图形学、地理信息系统和机器人学等）众多的应用领域中，几何算法都发挥了重要的作用。 许多解决几何问题的早期算法，要么速度很慢，要么难于理解与实现。随着近年来一些新的算法技术的发展，此前的很多方法都得到了改进与简化。这本教材力图使得这些现代的算法能够为更广泛的读者理解和接受。本书既是面向计算几何课程的一本教材，同时也可用于自学。 本书的结构。除导言外，这16章中的每一章都从来自应用领域的某一实际问题入手。这个问题将被转化为一个纯粹的几何问题，进而通过计算几何所提供的方法加以解决。每章所讨论的，实质上就是对应的那个几何问题，以及解决该问题所需要的概念与方法。我们根据所希望覆盖的计算几何专题，来选取有关的应用；而就具体的应用领域而言，这些介绍还远远不够全面。引入这些应用的目的，只是为了激发读者的兴趣；而各章本身的目的，并不在于为这些问题提供现成可用的解决方法。虽然如此，我们还是认为，为有效地解决应用中的几何问题，计算几何方面的知识是非常重要的。希望本书不仅能够吸引来自算法学术圈的那些人，而且对来自应用领域的人们亦是如此。 同一几何问题，可能有好几种不同的解决方法，不过，在论述大多数几何问题时，我们将只给出其中一种。我们通常所选取的，都是最易于理解与实现的方法。我们也十分注意，尽力使本书能够涵盖更多的方法，比如分治策略、平面扫描以及随机算法（randomized algorithm）等等。对每个问题可能的种种变型，我们也不打算面面俱到；我们觉得，更重要的是首先对计算 几何中的各个主要问题做一介绍，而不是过于深入地去探究少数专题的细枝末节。 某些章的若干节标有星号。这些节的内容涉及解法的改进与扩展，或者解释了不同问题之间的相互关联。就对后续章节的理解而言，它们并不十分重要。 每章最后，都由名为“注释及评论”的一节进行概括总结。这些节会给出对应各章所介绍结果的来龙去脉，概述其他的解决方法、一般化处理方法及改进，并给出参考文献。虽然这些节可以被跳过，但是对于那些希望就某一章的专题做进一步了解的读者来说，其中的材料都是非常有用的。 每章后面，都附有一定数量的习题。其中一些旨在检查读者对内容的理解程度，也有些是对书中内容的推广，需要精心解答。高难度的问题以及对应于标有星号各节的问题，也被标上星号。 课程大纲。尽管在很大程度上，本书各章之间是相互独立的，但在进行介绍时，最好还是不要随意打乱其次序。例如，第2章介绍了平面扫描算法，故在阅读采用了这一方法的其他各章之前，最好首先了解该章的内容。出于同样考虑，在进入有关随机算法的各章之前，也应该首先阅读第4章。 如果是作为计算几何的第一门课程，建议（教师）按照书中的次序来讲授前十章。根据我们的经验，这十章覆盖了任何一门计算几何课程都必须介绍的概念和方法。如果还有可能顾及更多的内容，可以在后面六章中进行挑选。 先修要求。作为教材，本书既适用于高年级本科生课程，也适用于低年级研究生课程，具体安排视课程的其他要求而定。读者应具备算法设计与分析、数据结构的基本知识：必须熟知大O记号，以及诸如排序、二分查找和平衡查找树等基本的算法技术。读者不需要对这里所涉及的应用领域有所了解，也几乎不需要什么几何知识。在对随机算法进行分析时，会用到一些非常基本的概率理论。 实现。本书中的算法都是以伪代码的形式给出，虽略显概括笼统，但也算详尽，实现起来相对容易。值得一提的是，我们还尝试着介绍了处理退化情况的方法，在具体实现过程中如不能解决好这一问题，往往会使整个计划落空。 我们认为，动手实现其中一个或多个算法将十分有益；这可以令你获得对算法复杂度的实际感受。每一章都可以当成一个编程训练的课程项目。根据可利用时间的多少，你既可以只实现算法本身，也可以连同应用系统一起完成。 为了实现一个几何算法，若干基本的数据类型??点、直线和多边形等??以及对其实施操作的一些基本例程都是必需的。实现这些基本例程并使之具有鲁棒性，绝非易事，为此需要投入大量的时间。自己动手这样做一次不无裨益，然而如果能够找到一个提供基本数据类型及其操作例程的现成的软件库，将很有帮助。在我们的万维网页面上，可以找到指向这类软件库的链接。 万维网站。本书还附有一个万维网站，该网站提供了本书各个版本的勘误、所有插图、所有算法的伪代码，以及一些其他资源。其地址是： http://www.cs.uu.nl/geobook/ 如果您发现了书中的错误，或是对本书有何建议，可以通过该页面与我们联系。 关于第3版。第3版的改动主要有两处：第7章“Voronoi图：邮局问题”中，增加了关于线段Voronoi图、最远点Voronoi图的讨论；第12章“空间二分：画家算法”中，针对低密度场景的BSP树，作为实际输入模型的导论，增加了一节。此外，更正了大量瑕疵与错误（请参阅网站提供的第2版勘误）。每章的“注释及评论”一节也做了更新，以体现新的研究成果及相关文献。为不致影响学生继续在课程学习中沿用第2版，第3版尽可能没有改动原先各节与各习题的编号。 致谢。编写教材是一项耗时的工作，即便有四位作者共同合作，也不例外。在过去几年中我们得到了很多人的帮助：关于本书应该包括、不应该包括哪些内容，有些人提供了有益的建议，有些人在阅读初稿后对如何修改提出了建议，另一些人则指出并更正了前两版中的错误。感谢所有这些人，特别要感谢Pankaj Agarwal、Helmut Alt、Marshall Bern、Jit Bose、Hazel Everett、Gerald Farin、Steve Fortune、Geert-Jan Giezeman、Mordecai Golin、Dan Halperin、Richard Karp、Matthew Katz、Klara Kedem、Nelson Max、Joseph S. B. Mitchell、Rene van Oostrum、Gunter Rote、Henry Shapiro、Sven Skyum、Jack Snoeyink、Gert Vegter、Peter Widmayer、Chee Yap和Gunther Ziegler。感谢Springer-Verlag出版社给予的建议和支持，使得本书各版本得以出版，并被译成日文、中文及波兰文。 最后，还要感谢荷兰科学研究组织（Netherlands Organization for Scientific Research-N. W. O.）与韩国研究基金（Korea Research Foundation-KRF）的大力支持。 Mark de Berg Otfried Cheong Marc van Kreveld Mark Overmars

版权图片链接