众所周知，几何学的历史至少可追述至古希腊时代，但不同人对“计算几何”的理解却不尽相同。本课程讨论的计算几何，源自于古典离散/组合几何学与现代计算机科学的结合。M. I. Shamos在1978年完成的博士论文，标志着这个学科分支的诞生。从那时起，“计算几何”往往特指针对离散与组合几何结构的算法研究。简而言之，她也可认为是算法设计与分析的几何版。 本课程的教学目标有三： 其一、对计算几何理论的总体认识，在日后的研究工作中，这种认识为你提供几何的视角。其次、对几何问题求解范式及策略的全面领会，包括递增式构造、平面扫描、分而治之、分层化、近似以及随机化等。最后、对基本几何结构及其算法的透彻掌握，包括凸包、多边形细分、Voronoi图、Delaunay三角剖分，以及几何求交、点定位、范围查找、截窗查询等。
Overview
Syllabus
- 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
- 期末考试
Taught by
Junhui Deng
