计算几何(自主模式)

自主模式

  • 什么是随堂模式?

    随堂模式课程一般为每学期一轮次,课程每周更新,作业、考试有截止时间,由课程提供方老师、助教指导,课程完结,成绩由老师确认后,统一发放证书。

  • 什么是自主模式?

    自主模式课程常年开放加入,课件全部开放,作业、考试无截止时间,有学堂在线招募选拔的助教指导,考核通过即可自动获得证书。

来自于: 清华大学 | 分类: 计算机(280)

课程描述

体味几何之趣,领悟算法之美

什么是认证证书?
免费学习
认证学习
名师签名
实名认证
权威性
纸质证书
付费购买
免费赠送

课程简介

众所周知,几何学的历史至少可追述至古希腊时代,但不同人对“计算几何”的理解却不尽相同。本课程讨论的计算几何,源自于古典离散/组合几何学与现代计算机科学的结合。M. I. Shamos在1978年完成的博士论文,标志着这个学科分支的诞生。从那时起,“计算几何”往往特指针对离散与组合几何结构的算法研究。简而言之,她也可认为是算法设计与分析的几何版。

本课程的教学目标有三:

其一、对计算几何理论的总体认识,在日后的研究工作中,这种认识为你提供几何的视角

其次、对几何问题求解范式及策略的全面领会,包括递增式构造、平面扫描、分而治之、分层化、近似以及随机化等

最后、对基本几何结构及其算法的透彻掌握,包括凸包、多边形细分、Voronoi图、Delaunay三角剖分,以及几何求交、点定位、范围查找、截窗查询等

展开

课程章节

00. Introduction
Before we start
Evaluation
Online Judge
Lecture notes
Discussion
A. History of This Course
B. What's Computational Geometry
C. How to Learn CG Better
D. Why English
01. Convex Hull
A. Convexity
B. Extreme Points
C. Extreme Edges
D. Incremental Construction
E. Jarvis March
F. Lower Bound
G. Graham Scan: Algorithm
H. Graham Scan: Example
I. Graham Scan: Correctness
J. Graham Scan: Analysis
K. Divide-And-Conquer (1)
L. Divide-And-Conquer (2)
M. Wrap-Up
02. Geometric Intersection
0. Introduction
A. Preliminary
B. Interval Intersection Detection
C. Segment Intersection Reporting
D. BO Algorithm: Strategy
E. BO Algorithm: Implementation
F. BO Algorithm: Analysis
G. Convex Polygon Intersection Detection
H. Edge Chasing
I. Plane Sweeping
J. Halfplane Intersection Construction
03. Triangulation
0. Methodology
A. Art Gallery Problem
B. Art Gallery Theorem
C. Fisk's Proof
D. Orthogonal Polygons
E. Triangulation
F. Triangulating Monotone Polygons
G. Monotone Decomposition
I. Tetrahedralization
04. Voronoi Diagram
A. Introduction
B. Terminologies
C. Properties
D. Complexity
E. Representation
F. DCEL
G. Hardness
H. Sorted Sets
I. VD_sorted
J. Naive Construction
K. Incremental Construction
L. Divide-And-Conquer
M. Plane-Sweep
05. Delaunay Triangulation
A. Point Set Triangulation
B. Delaunay Triangulation
C. Properties
D. Proximity Graph
E. Euclidean Minimum Spanning Tree
F. Euclidean Traveling Salesman Problem
G. Minimum Weighted Triangulation
H. Construction
I. RIC With Example
J. Randomized Incremental Construction
K. RIC Analysis
06. Point Location
0. Online/Offline Algorithms
A. Introduction
B. Slab Method
C. Persistence
D. Path Copying
E. Node Copying
F. Limited Node Copying
G. Kirkpatrick Structure
H. Trapezoidal Map
I. Constructing Trapezoidal Map
J. Performance Of Trapezoidal Map
07. Geometric Range Search
A. Range Query
B. BBST
C. kd-Tree: Structure
D. kd-Tree: Algorithm
E. kd-Tree: Performance
F. Range Tree: Structure
G. Range Tree: Query
H. Range Tree: Performance
I. Range Tree: Optimization
08. Windowing Query
A. Orthogonal Windowing Query
B. Stabbing Query
C. Interval Tree: Construction
D. Interval Tree: Query
E. Stabbing With A Segment
F. Grounded Range Query
G. 1D-GRQ Using Heap
H. Priority Search Tree
I. 2D-GRQ Using PST
J. Segment Tree
K. Vertical Segment Stabbing Query
Final Test
Problem Assignments
Final Test

授课教师

  • 邓俊辉清华大学 计算机系 副教授

    邓俊辉,清华大学计算机系副教授。1993、1995和1997年分别于清华大学计算机系获学士、硕士和博士学位,1997年起在清华大学任教,主要讲授“数据结构”和“计算几何”。

精华笔记

精华笔记正在评选中,去看看全部笔记

常见问题

课程有讲义吗?

每个视频都有对应的pdf讲义

我需要看课程直播吗?

不需要,你可以在闲暇时间学习。

我能联系老师和助教吗?

能,但不是直接,可以在课程讨论区提问有关课程的问题,老师会解答一些重要的题,其他学生的解答将会更加充分和快速。

这门课程的课本是什么?

课程有讲义提供下载,课程参考书请参见第0章。

课程成绩如何评定?

最终成绩由以下两个方面累计而得:期末考试占60%,编程习题占40%