- From www.xuetangx.com
计算几何（2016春）
Course
zh
Chinese
This content is rated 0 out of 5
- Introductive Level
- Starts on March 28, 2016
Course details
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. Pririty Search Tree
- I. 2D-GRQ Using PST
- J. Segment Tree
- K. Vertical Segment Stabbing Query
- Final Test
- Final Test
Prerequisite
None.
Instructors
- 邓俊辉
Platform
Founded by Tsinghua University in October 2013, XuetangX is the world’s first Chinese MOOC platform and serves as the research and application platform for the Ministry of Education (MOE) Research Center for Online Education. XuetangX has been awarded as one of the national first batch of demonstration base projects for innovation and entrepreneurship. Besides, XuetangX also works with the International Center for Engineering Education (ICEE) under the auspices of UNESCO and supports its online portion. By the end of June 2018, with a total of 25 million enrollments and more than 1,500 online courses from 13 disciplined fields, XuetangX has accumulated over 12 million registered users, covering 209 countries and regions.
This content is rated 4.5 out of 5
(no review)This content is rated 4.5 out of 5
(no review)Complete this resource to write a review