几何算法是一类用于解决几何图形及其属性相关问题的计算方法。这些算法处理的对象包括点、线、多边形和其他几何图形。

在计算机科学的许多领域，如机器人学、计算机制图、虚拟现实和地理信息系统，都需要存储、分析、创建或处理空间数据。本课程涉及这些任务的算法方面：我们将学习设计和分析几何算法和数据结构所需的技术和概念。每种技术和概念都将以上述应用领域中出现的一个问题为基础进行说明。 目标：在本课程结束时，学员应能够--决定使用哪种算法或数据结构来解决给定的基本几何问题，--分析新问题，并使用课程中的概念和技术提出自己的有效解决方案。 先决条件：为了成功学习本课程，您应具备算法和数学的基础知识。以下是您应该了解的内容的简短列表： - O-注解、Ω-注解、Θ-注解；如何分析算法 - 基本微积分：操作求和、求解递归、使用对数等 - 基本概率论：事件、概率分布、随机变量、期望值等。 - 基本数据结构：链表、二叉搜索树等 - 图形术语 - 实际作业的编程技巧 本课程的大部分材料基于以下书籍：M. de Berg、O. Cheong、M. van Kreveld 和 M. Overmars。计算几何：算法与应用》（第 3 版）。Springer-Verlag 出版社，2008 年。但是，如果学员想了解比本课程更多的知识，或者想再次了解讲座中讨论的材料，我们建议购买这本书。 视频讲座包含一些非常小的错误。这些错误的清单可在资源下找到。如果您认为发现了错误，请单击讲座或测验底部的方形标志报告问题。