体味几何之趣,领悟算法之美
播放:38159次,课程ID:4231548
体味几何之趣,领悟算法之美
--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
--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
--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
--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
--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
--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
--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
--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
--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
邓俊辉,清华大学计算机系教授。1993和1997年分别于清华大学计算机系获学士、博士学位,1997年起在清华大学任教,他在讲授“数据结构”和“计算几何”方面拥有20多年的经验。