- Sur www.xuetangx.com
计算几何(2016春)
- Niveau Introductif
- Débute le 28 mars 2016
Détails du cours
Déroulé
- 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. Pririty Search Tree
- I. 2D-GRQ Using PST
- J. Segment Tree
- K. Vertical Segment Stabbing Query
- Final Test
- Final Test
Prérequis
Intervenants
- 邓俊辉
Plateforme
Fondée par l'Université Tsinghua en octobre 2013, XuetangX est la première plateforme MOOC chinoise au monde et sert de plate-forme de recherche et d'application au Centre de recherche pour la formation en ligne du ministère de l'Éducation. XuetangX a été primé parmi le premier groupe national de projets de base de démonstration pour l'innovation et l'entrepreneuriat. Par ailleurs, XuetangX collabore également avec le Centre international de formation des ingénieurs (ICEE) sous les auspices de l’UNESCO et soutient sa partie en ligne. À la fin de juin 2018, avec un total de 25 millions d'inscriptions et plus de 1 500 cours en ligne dans 13 disciplines différentes, XuetangX a accumulé plus de 12 millions d'utilisateurs enregistrés, répartis dans 209 pays et régions.