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.
Geometric Algorithms
EIT 数字課程信息
5,386 次近期查看
可分享的證書
完成後獲得證書
100% 在線
立即開始，按照自己的計劃學習。
可靈活調整截止日期
根據您的日程表重置截止日期。
中級
完成時間大約為18 小時
英語（English）
字幕：英語（English）
可分享的證書
完成後獲得證書
100% 在線
立即開始，按照自己的計劃學習。
可靈活調整截止日期
根據您的日程表重置截止日期。
中級
完成時間大約為18 小時
英語（English）
字幕：英語（English）
提供方
EIT 数字
EIT Digital is a pan-European organization whose mission is to foster digital technology innovation and entrepreneurial talent for economic growth and quality of life. By linking education, research and business, EIT Digital empowers digital top talents for the future.
教學大綱 - 您將從這門課程中學到什麼
完成時間為 7 小時
Plane Sweep Algorithms
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.
完成時間為 7 小時
4 個視頻 （總計 25 分鐘）
4 個視頻
Introduction5分鐘
Plane Sweep: Concept6分鐘
Data Structures for Plane Sweep Algorithms8分鐘
Line Sweep: Missing Parts4分鐘
4 個練習
Plane Sweep: Concept15分鐘
Data Structures for Plane Sweep Algorithms20分鐘
Line Sweep: missing parts20分鐘
Line Sweep Algorithms15分鐘
完成時間為 7 小時
Voronoi diagrams and Delaunay triangulations
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.
完成時間為 7 小時
8 個視頻 （總計 45 分鐘）
8 個視頻
Voronoi Diagrams: Structure4分鐘
Complexity of Voronoi Diagrams4分鐘
Delaunay Triangulations5分鐘
Angle-Optimal Triangulations6分鐘
Legal Triangulations5分鐘
Randomized Incremental Construction4分鐘
Randomized Incremental Construction: Analysis10分鐘
4 個練習
Voronoi15分鐘
Triangulations15分鐘
Randomized incremental construction20分鐘
Voronoi Diagrams and Delaunay triangulations15分鐘
完成時間為 4 小時
Orthogonal range searching
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.
完成時間為 4 小時
6 個視頻 （總計 43 分鐘）
6 個視頻
1D Range Searching6分鐘
KD Trees5分鐘
Queries in KD-Trees7分鐘
Range Trees7分鐘
Range Trees: Extensions10分鐘
3 個練習
KD-trees20分鐘
Range Trees20分鐘
KD and range trees30分鐘
常見問題
我什么时候能够访问课程视频和作业？
讲座和作业的访问权限取决于您的注册类型。如果您以旁听模式参加课程，则可以免费查看大多数课程资料。要访问评分作业并获得证书，您需要在旁听期间或之后购买证书体验。如果看不到旁听选项：
- 课程可能不提供旁听选项。您可以尝试免费试用，也可以申请助学金。
- 课程可能会改为提供'完整课程，没有证书'。通过此选项，您可以查看所有课程材料、提交所要求的作业，以及获得最终成绩。这也意味着您将无法购买证书体验。
我购买证书后会得到什么？
您购买证书后，将有权访问所有课程材料，包括评分作业。完成课程后，您的电子课程证书将添加到您的成就页中，您可以通过该页打印您的课程证书或将其添加到您的领英档案中。如果您只想阅读和查看课程内容，可以免费旁听课程。
退款政策是如何规定的？
您可在付款后两周内，或者在课程第一个班次开课后（对于已启动的课程）两周内，获得全额退款，以其中较晚者为准。获得课程证书后，您便无法再退款；即使您在两周的退款期内完成了课程，也是如此。请阅读我们完整的退款政策。
有助学金吗？
是的，Coursera 可以向无法承担学费的学生提供助学金。点击左侧‘注册’按钮下的‘助学金’链接即可申请助学金。您可以根据屏幕提示完成申请，申请获批后会收到通知。了解详情。
完成课程后，我会获得大学学分吗？
此课程不提供大学学分，但部分大学可能会选择接受课程证书作为学分。查看您的合作院校，了解详情。Coursera 上的在线学位和 Mastertrack™ 证书提供获得大学学分的机会。
還有其他問題嗎？請訪問 學生幫助中心。
