|
所在平台: Coursera |
课程主页: https://www.coursera.org/learn/geometric-algorithms
课程评论：没有评论
课程名称：几何算法 课程概述：在计算机科学的多个领域，如机器人技术、计算机图形学、虚拟现实和地理信息系统，存储、分析以及创建或操作空间数据是非常必要的。本课程关注这些任务的算法方面，学习设计和分析几何算法及数据结构所需的技术与概念。每个技术和概念将通过来自上述应用领域的问题进行阐释。 课程目标： 完成本课程后，参与者应能够： - 决定在解决特定基本几何问题时应使用哪种算法或数据结构； - 分析新问题，并利用课程中的概念和技术提出高效的解决方案。 先修要求： 为了成功参加本课程，学员应具备基础的算法和数学知识。以下是需要掌握的知识内容： - O-符号、Ω-符号、Θ-符号；如何分析算法； - 基础微积分：操作求和、解决递归、处理对数等； - 基础概率论：事件、概率分布、随机变量、期望值等； - 基础数据结构：链表、二叉搜索树等； - 图的术语； - 实践作业的编程技能。 本课程的大部分材料基于以下书籍： M. de Berg, O. Cheong, M. van Kreveld, 和 M. Overmars著《计算几何：算法与应用》（第三版）。Springer-Verlag, 2008。 购买此书并非强制，但如果参与者希望了解超出课程内容的信息或想复习讲座中讨论的材料，建议购买此书。 视频讲座中可能存在一些非常小的错误，相关错误列表可以在资源部分找到。如果您认为发现了错误，请通过点击课程或测验底部的方形标志报告问题。 课程大纲： 1. 平面扫描算法 - 该模块讨论一个线段相交的算法，该算法不仅依赖于输入大小（即线段数量），还取决于输出大小（即交点数量）。该算法使用平面扫描技术，适用于许多在欧几里得平面中的算法问题。 2. Voronoi图和Delaunay三角剖分 - 本模块介绍Voronoi图和Delaunay三角剖分的概念及其性质。此外，我们将通过随机增量构造技术介绍构建Delaunay三角剖分的算法，并分析这类算法。 3. 正交范围搜索 - 本模块引入范围搜索问题。我们将首先研究一维情况，随后推广到更高维度。我们将探索两种支持范围搜索的数据结构，即KD树和范围树，并通过构造时间、空间使用和查询时间对它们进行比较。
Name:Plane Sweep Algorithms
Description:In this module we will discuss an algorithm for line segment intersection that does not only depend on the input size, i.e. the number of line segments, but also on the output size, i.e. the number of intersections. This algorithm uses the Plane Sweep technique, which is applicable to many algorithmic problems in the Euclidean plane.
Name:Voronoi diagrams and Delaunay triangulations
Description:In this module we will introduce the notions of Voronoi diagrams and Delaunay triangulations and its properties. Furthermore we will an algorithm for constructing Delaunay triangulations using the technique of randomized incremental construction. We will see how to analyze these types of algorithms.
Name:Orthogonal range searching
Description:In this module we will introduce the problem of range searching. We will first look at the one dimensional case and later on generalize to higher dimensions. We will see two data structures that allow for range searching, namely KD Trees and Range Trees. We will compare them by looking at construction time, space usage and query time.
Course Information: In many areas of computer science such as robotics, computer graphics, virtual reality, and geographic information systems, it is necessary to store, analyze, and create or manipulate spatial data. This course deals with the algorithmic aspects of these tasks: we study techniques and concepts needed for the design and analysis of geometric algorithms and data structures. Each technique and concept will be illustrated on the basis of a problem arising in one of the application areas mentioned above. Goals: At the end of this course participants should be able - to decide which algorithm or data structure to use in order to solve a given basic geometric problem, - to analyze new problems and come up with their own efficient solutions using concepts and techniques from the course. Prerequisites: In order to successfully take this course, you should already have a basic knowledge of algorithms and mathematics. Here's a short list of what you are supposed to know: - O-notation, Ω-notation, Θ-notation; how to analyze algorithms - Basic calculus: manipulating summations, solving recurrences, working with logarithms, etc. - Basic probability theory: events, probability distributions, random variables, expected values etc. - Basic data structures: linked lists, binary search trees, etc. - Graph terminology - Programming skills for practical assignments Most of the material in this course is based on the following book: M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars. Computational Geometry: Algorithms and Applications (3rd edition). Springer-Verlag, 2008. It is not mandatory to buy this book. However if participants want to know more than is offered in this course or want to have another look at the material discussed in the lectures, we recommend buying this book. The video lectures contain a few very minor mistakes. A list of these mistakes can be found under resources. If you think you found an error, report a problem by clicking the square flag at the bottom of the lecture or quiz where you found the error.
