We're sorry this project doesn't work properly without JavaScript enabled. Please enable it to continue.
欢迎来到在线教学平台
问题答疑
首页
全部课程
公开课
云课直播
新闻公告
数图资源
智汇大讲堂
更多
  • 扫码下载Android
  • 扫码下载iOS
首页
全部课程
公开课
云课直播
新闻公告
数图资源
智汇大讲堂
    • 首页 - 课程列表 - 课程详情
    返回
    计算几何
    课程类型：选修课
    发布时间：2022-09-27 09:44:24
    主讲教师：邓俊辉
    课程来源：清华大学
    建议学分：0.00分
    课程编码：xtzx1955
    课程介绍
    课程目录
    教师团队
    00. Introduction
    A. History of This Course （5分钟）
    B. What's Computational Geometry （6分钟）
    C. How to Learn CG Better （7分钟）
    D. Why English （8分钟）
    01. Convex Hull
    01-A-01. Why Convex Hull （3分钟）
    01-A-02. Nails In The Table （3分钟）
    01-A-03. Paint Blending （6分钟）
    01-A-04. Color Space （6分钟）
    01-A-05. Convex Hull （7分钟）
    01-B-01. Extremity （5分钟）
    01-B-02. Strategy （3分钟）
    01-B-03. In-Triangle Test （5分钟）
    01-B-04. To-Left Test （6分钟）
    01-B-05. Determinant （4分钟）
    01-C-01. Definition （4分钟）
    01-C-02. Algorithm （5分钟）
    01-C-03. Demonstration （2分钟）
    01-D-01. Decrease and Conquer （6分钟）
    01-D-02. In-Convex-Polygon Test （7分钟）
    01-D-03. Why Not Binary Search （5分钟）
    01-D-04. Support-Lines （3分钟）
    01-D-05. Pattern Of Turns （4分钟）
    01-D-06. Exterior/Interior （3分钟）
    01-E-01. Selectionsort （3分钟）
    01-E-02. Strategy （5分钟）
    01-E-03. Coherence （3分钟）
    01-E-04. To-Left Test （5分钟）
    01-E-05. Degeneracy （2分钟）
    01-E-06. Lowest-Then-Leftmost （4分钟）
    01-E-07. Implementation （5分钟）
    01-E-08. Output Sensitivity （5分钟）
    01-F-01. Reduction （6分钟）
    01-F-02. CAO Chong's Methodology （3分钟）
    01-F-03. Transitivity （3分钟）
    01-F-04. Reduction: Input （5分钟）
    01-F-05. Reduction: Output （5分钟）
    01-F-06. Sorting ≤_N 2d-CH （3分钟）
    01-G-01. Preprocessing （5分钟）
    01-G-02. Scan （4分钟）
    01-G-03. Simplest Cases （5分钟）
    01-H-01. Example (1/2) （6分钟）
    01-H-02. Example (2/2) （5分钟）
    01-I-01. Left Turn （6分钟）
    01-I-02. Right Turn （5分钟）
    01-I-03. Presorting （5分钟）
    01-J-01. Ω(n) Backtracks （4分钟）
    01-J-02. Planarity （4分钟）
    01-J-03. Amortization （6分钟）
    01-J-04. Simplification （10分钟）
    01-K-02. Common Kernel （4分钟）
    01-K-03. Interior （6分钟）
    01-K-04. Exterior （5分钟）
    01-L-01. Preprocessing （4分钟）
    01-L-02. Common Tangents （3分钟）
    01-L-03. Topmost + Bottommost ? （3分钟）
    01-L-04. Stitch （5分钟）
    01-L-05. Zig-Zag （7分钟）
    01-L-06. Time Cost （3分钟）
    01-L-07. More Considerations （6分钟）
    01-M. Wrap-Up （5分钟）
    02. Geometric Intersection
    02-0. Introduction （6分钟）
    02-A-01. EU （4分钟）
    02-A-02. Min-Gap （5分钟）
    02-A-03. Max-Gap （5分钟）
    02-A-04. IEU （2分钟）
    02-B-01. Algorithm （5分钟）
    02-B-02. Lower Bound （4分钟）
    02-C-01. Brute-force （5分钟）
    02-C-02. Hardness （6分钟）
    02-D-01. Proximity & Separability （5分钟）
    02-D-02. Comparability & Ordering （7分钟）
    02-D-03. Data Structures （3分钟）
    02-D-04. Possible Cases （8分钟）
    02-E-01. Degeneracy （4分钟）
    02-E-02. Event Queue （4分钟）
    02-E-03. Events & Operations （4分钟）
    02-E-04. Sweepline Status （2分钟）
    02-F-01. Correctness （4分钟）
    02-F-02. Example （4分钟）
    02-F-03. Retesting （3分钟）
    02-F-04. Complexity of Event Queue （6分钟）
    02-F-05. Complexity of Status Structure （4分钟）
    02-G-01. Problem Specification （4分钟）
    02-G-02. Monotone Partitioning （3分钟）
    02-G-03. Criterion （5分钟）
    02-G-04. Decrease-And-Conquer （4分钟）
    02-G-05. Example Cases （4分钟）
    02-G-06. Complexity （2分钟）
    02-H-01. Eliminating Sickles （5分钟）
    02-H-02. Example （4分钟）
    02-H-03. Analysis （3分钟）
    02-I. Plane Sweeping （7分钟）
    02-J-01. The Problem （4分钟）
    02-J-02. Lower Bound （7分钟）
    02-J-03. Divide-And-Conquer （4分钟）
    03. Triangulation
    03-0. Methodology （5分钟）
    03-A-01. Definition （5分钟）
    03-A-02. Lower & Upper Bounds （5分钟）
    03-A-03. Hardness （4分钟）
    03-A-04. Approximation & Classification （3分钟）
    03-B-01. Necessity of floor(n/3) （4分钟）
    03-B-02. Sufficiency by Fan Decomposition （4分钟）
    03-C-01. Triangulation （4分钟）
    03-C-02. 3-Coloring （5分钟）
    03-C-03. Domination （3分钟）
    03-C-04. Pigeon-Hole Principle （3分钟）
    03-C-05. Generalization （3分钟）
    03-D-01. Necessity of floor(n/4) （3分钟）
    03-D-02. Sufficiency by Convex Quadrilateralization （3分钟）
    03-D-03. Generalization （2分钟）
    03-E-01. Existence （7分钟）
    03-E-02. Ear & Mouth （4分钟）
    03-E-03. Two-Ear Theorem （4分钟）
    03-E-04. Well-Order （6分钟）
    03-E-05. Ear Candidate （5分钟）
    03-E-06. Induction （6分钟）
    03-E-07. Well-Order (Again) （3分钟）
    03-E-08. Properties （7分钟）
    03-F-01. Monotone Polygon （6分钟）
    03-F-02. Monotonicity Testing （3分钟）
    03-F-03. Strategy （5分钟）
    03-F-04. Stack-Chain Consistency （4分钟）
    03-F-05. Same Side + Reflex （3分钟）
    03-F-06. Same Side + Convex （4分钟）
    03-F-07. Opposite Side （6分钟）
    03-F-08. Example （6分钟）
    03-F-09. Analysis （5分钟）
    03-G-01. Cusps （7分钟）
    03-G-02. Helper （5分钟）
    03-G-03. Helper Candidate （3分钟）
    03-G-04. Sweep-Line Status （2分钟）
    03-G-05. Possible Cases （8分钟）
    03-G-06. Example （6分钟）
    03-G-07. Analysis （6分钟）
    03-I-01. Polyhedron Decomposition （3分钟）
    03-I-02. Schonhardt's Polyhedron （5分钟）
    03-I-03. Seidel's Polygon （6分钟）
    04. Voronoi Diagram
    04-A-01. A First Glance （3分钟）
    04-A-02. Dining Halls on Campus （3分钟）
    04-A-03. More Analogies & Applications （4分钟）
    04-A-04. Voronoi （2分钟）
    04-B-01. Site & Cell （3分钟）
    04-B-02. Intersecting Halfspaces （3分钟）
    04-B-03. Voronoi Diagram （3分钟）
    04-B-04. Planar Voronoi Diagram （3分钟）
    04-C-01. Non-Empty Cells （3分钟）
    04-C-02. Empty Disks （6分钟）
    04-C-03. Nearest = Concyclic （3分钟）
    04-C-04. Number of Nearest Sites = Degree （5分钟）
    04-C-05. Split & Merge （5分钟）
    04-D-01. Linearity （4分钟）
    04-D-02. Proof （6分钟）
    04-E-01. Subdivision （5分钟）
    04-E-02. Fary's Theorem （3分钟）
    04-E-03. Representing VD （3分钟）
    04-F-01. Twin Edges （3分钟）
    04-F-02. Half-Edge （5分钟）
    04-F-03. Vertex & Face （4分钟）
    04-F-04. Traversal （5分钟）
    04-F-05. True Or False （1分钟）
    04-F-06. Application （2分钟）
    04-G-01. 1D Voronoi Diagram （9分钟）
    04-G-02. 2D Voronoi Diagram （6分钟）
    04-G-03. Voronoi Diagram In General Position （4分钟）
    04-H-01. Convex Hull Made Easier （4分钟）
    04-H-02. Convex Hull As A Combinatorial Structure （3分钟）
    04-H-03. Voronoi Diagram As A Geometric Structure （5分钟）
    04-I-01. ε-Closeness （5分钟）
    04-I-02. Lifting （4分钟）
    04-I-03. Projection （6分钟）
    04-I-04. Case A （4分钟）
    04-I-05. Case B （5分钟）
    04-I-06. Sorting Not Made Easier （2分钟）
    J. Naive Construction （7分钟）
    04-K-01. Royal Garden （4分钟）
    04-K-02. Disjoint Union （6分钟）
    04-K-03. Complexity （5分钟）
    04-L-01. Strategy （6分钟）
    04-L-02. Solving Overlaps （5分钟）
    04-L-03. Contour （5分钟）
    04-L-04. Bisectors （3分钟）
    04-L-05. Y-Monotonicity （2分钟）
    04-L-06. Common Tangents （3分钟）
    04-L-07. Contour Length （3分钟）
    04-L-08. Clip & Stitch （7分钟）
    04-L-09. Intersecting with Cells （5分钟）
    04-L-10. Convexity （5分钟）
    04-L-11. Avoiding Rescans （4分钟）
    04-M-01. A First Glance （2分钟）
    04-M-02. Backtracking （5分钟）
    04-M-03. Fortune's Trick （3分钟）
    04-M-04. Frozen Region （4分钟）
    04-M-05. Beach Line （4分钟）
    04-M-06. Lower Envelope （6分钟）
    04-M-07. Break Points （5分钟）
    04-M-08. Events （4分钟）
    04-M-09. Circle Event: What, When & Where （4分钟）
    04-M-10. Circle Event: Why （5分钟）
    04-M-11. Circle Event: How （5分钟）
    04-M-12. Site Event: What （6分钟）
    04-M-13. Site Event: How （8分钟）
    05. Delaunay Triangulation
    05-A-01. Definition （6分钟）
    05-A-02. Edge Flipping （8分钟）
    05-A-03. Upper Bound （7分钟）
    05-A-04. Lower Bound （7分钟）
    05-B-01. Dual Graph （5分钟）
    05-B-02. Triangulation （2分钟）
    05-B-03. Hardness （3分钟）
    05-B-04. History （3分钟）
    05-C-01. Empty Circumcircle （4分钟）
    05-C-02. Empty Circle （3分钟）
    05-C-03. Nearest Neighbor （4分钟）
    05-C-04. Complexity （3分钟）
    05-D-01. Gabriel Graph （10分钟）
    05-D-02. Relative Neighborhood Graph （5分钟）
    05-D-03. Lower Bounds （4分钟）
    05-E-01. Definition （4分钟）
    05-E-02. Construction （4分钟）
    05-E-03. Subgraph of RNG （7分钟）
    05-E-04. Example （4分钟）
    05-F-01. Definition （2分钟）
    05-F-02. NP-Hardness （3分钟）
    05-F-03. Approximation （7分钟）
    05-G-01. Definition （3分钟）
    05-G-02. Counter-Example （4分钟）
    05-G-03. Hardness （2分钟）
    05-H-01. Subtended Arc （4分钟）
    05-H-02. Angle Vector （4分钟）
    05-H-03. Maximizing The Minimum Angle （3分钟）
    05-H-04. Evolution By Edge Flipping （4分钟）
    05-H-05. Strategies （2分钟）
    05-I-01. Idea （3分钟）
    05-I-02. Point Location （2分钟）
    05-I-03. In-Circle Test （2分钟）
    05-I-04. Edge Flipping （2分钟）
    05-I-05. Frontier （3分钟）
    05-I-06. Convergence （2分钟）
    05-J-01. Recursive Implementation （7分钟）
    05-J-02. Iterative Implementation （4分钟）
    05-J-03. In-Circle Test （5分钟）
    05-J-04. Point Location （6分钟）
    05-K-01. Time Cost （3分钟）
    05-K-02. Backward Analysis （3分钟）
    05-K-03. Preconditions （5分钟）
    05-K-04. Types Of Edge Change （3分钟）
    05-K-05. Number Of Edge Changes （6分钟）
    05-K-06. Average Degree （3分钟）
    05-K-07. Number Of Rebucketings （5分钟）
    05-K-08. Probability For Rebucketing （5分钟）
    05-K-09. Expectation （3分钟）
    05-K-10. Further Consideration （2分钟）
    06. Point Location
    06-0. Online/Offline Algorithms （3分钟）
    06-A-01. Where Am I （5分钟）
    06-A-02. Point Location （5分钟）
    06-A-03. Assumptions For Clarity （3分钟）
    06-A-04. Input Size （3分钟）
    06-A-05. Performance Measurements （5分钟）
    06-A-06. A Global View （5分钟）
    06-B-01. Slab Decomposition （6分钟）
    06-B-02. Ordering Trapezoids （4分钟）
    06-B-03. Tree of Trees （5分钟）
    06-B-04. Example （4分钟）
    06-B-05. Query Time （3分钟）
    06-B-06. Preprocessing Time （6分钟）
    06-B-07. Storage Cost （2分钟）
    06-B-08. Worst Case （5分钟）
    06-C-01. Ephemeral Structure （4分钟）
    06-C-02. Persistent Structure （4分钟）
    06-C-03. Persistent Slabs （3分钟）
    06-D-01. Strategy （5分钟）
    06-D-02. X-Search （3分钟）
    06-D-03. Storage Optimization （4分钟）
    06-E-01. O(1) Rotation （7分钟）
    06-E-02. Strategy （7分钟）
    06-E-03. Why Red-Black （6分钟）
    06-E-04. Linear Space （2分钟）
    06-E-05. Time Penalty （3分钟）
    06-F-01. Idea （3分钟）
    06-F-02. Split （3分钟）
    06-F-03. Complexity （4分钟）
    06-F-04. Recoloring （3分钟）
    06-G-01. Optimal And Simpler （3分钟）
    06-G-02. Triangulation （5分钟）
    06-G-03. Example （6分钟）
    06-G-04. Hierarchy （6分钟）
    06-G-05. Independent Subset （3分钟）
    06-G-06. The More The Better （3分钟）
    06-G-07. The Fewer The Better （3分钟）
    06-G-08. Degree （3分钟）
    06-G-09. Existence Of Independent Subset （4分钟）
    06-G-10. Construction Of Independent Subset （5分钟）
    06-G-11. DAG （8分钟）
    06-H-01. Ray Shooting （3分钟）
    06-H-02. Decomposition （2分钟）
    06-H-03. Properties & Complexity （3分钟）
    06-H-04. Search Structure: Example （6分钟）
    06-H-05. Search Structure: Nodes （4分钟）
    06-H-06. Search Structure: Performance （3分钟）
    06-I-01. Initialization （4分钟）
    06-I-02. Iteration （4分钟）
    06-I-03. Challenges （3分钟）
    06-I-04. Case 1: Two Endpoints （5分钟）
    06-I-05. Case 2: One Endpoint （5分钟）
    06-I-06. Case 3: No Endpoints （5分钟）
    06-I-07. Example （5分钟）
    06-J-01. Randomization （4分钟）
    06-J-02. Expectation （4分钟）
    06-J-03. Number Of Ray Trimmed （7分钟）
    06-J-04. Number Of Trapezoidals Created (1) （6分钟）
    06-J-05. Number Of Trapezoidals Created (2) （5分钟）
    06-J-06. Time For Point Location （2分钟）
    06-J-07. Size Of Search Structure （1分钟）
    06-J-08. Fixed Query Point + Randomly Created Maps （4分钟）
    06-J-09. Each Single Step （4分钟）
    06-J-10. Probability Of Enclosing Trapezoid Changed （3分钟）
    06-J-11. Query Time （5分钟）
    07. Geometric Range Search
    07-A-01. 1-Dimensional Range Query （6分钟）
    07-A-02. Brute-force （5分钟）
    07-A-03. Binary Search （5分钟）
    07-A-04. Output Sensitivity （5分钟）
    07-A-05. Planar Range Query （5分钟）
    07-B-01. Structure （4分钟）
    07-B-02. Lowest Common Ancestor （3分钟）
    07-B-03. Query Algorithm （6分钟）
    07-B-04. Complexity (1) （3分钟）
    07-B-05. Complexity (2) （6分钟）
    07-C-01. 2d-Tree （3分钟）
    07-C-02. Example （12分钟）
    07-C-03. Construction （5分钟）
    07-C-04. Example （5分钟）
    07-C-05. Canonical Subsets （4分钟）
    07-D-01. Query （10分钟）
    07-D-02. Example （8分钟）
    07-D-03. Optimization （7分钟）
    07-E-01. Preprocessing Time + Storage （5分钟）
    07-E-02. Query Time （9分钟）
    07-E-03. Beyond 2D （4分钟）
    07-F-01. x-Query + y-Query （4分钟）
    07-F-02. Worst Case （4分钟）
    07-F-03. x-Query * y-Queries （7分钟）
    07-G-01. Painters' Strategy （5分钟）
    07-G-02. X-Tree （5分钟）
    07-G-03. Y-Trees （4分钟）
    07-G-04. Algorithm （5分钟）
    07-H-01. Storage （9分钟）
    07-H-02. Preprocessing Time （2分钟）
    07-H-03. Query Time （4分钟）
    07-H-04. Beyond 2D （4分钟）
    07-I-01. Y-Lists （5分钟）
    07-I-02. Coherence （4分钟）
    07-I-03. Idea （3分钟）
    07-I-04. Fractional Cascading （9分钟）
    07-I-05. Complexity （7分钟）
    08. Windowing Query
    08-A-01. Definition （4分钟）
    08-A-02. Classification （5分钟）
    08-B-01. 1D Windowing Query （5分钟）
    08-B-02. Stabbing Query （6分钟）
    08-C-01. Median （3分钟）
    08-C-02. Partitioning （3分钟）
    08-C-03. Balance （4分钟）
    08-C-04. Associative Lists （4分钟）
    08-C-05. Complexity （3分钟）
    08-D-01. Algorithm (1) （8分钟）
    08-D-02. Algorithm (2) （6分钟）
    08-D-03. Complexity （4分钟）
    08-E-01. Definition （3分钟）
    08-E-02. Interval Tree （2分钟）
    08-E-03. Query Algorithm (1) （4分钟）
    08-E-04. Query Algorithm (2) （5分钟）
    08-E-05. Overview （4分钟）
    08-E-06. Complexity （6分钟）
    08-F-01. O(n) Space （3分钟）
    08-F-02. 2D-GRQ （4分钟）
    08-F-03. 1D-GRQ Using Range Tree （3分钟）
    08-F-04. 1D-GRQ By Linear Scan （4分钟）
    08-G-01. Heap （5分钟）
    08-G-02. Query （5分钟）
    08-G-03. Example （7分钟）
    08-G-04. Complexity （7分钟）
    08-H-01. PST = Heap + BBST （4分钟）
    08-H-02. Order Property （3分钟）
    08-H-03. Sibling Partitioning （6分钟）
    08-H-04. Construction （3分钟）
    08-I-01. Algorithm (1/2) （7分钟）
    08-I-02. Algorithm (2/2) （7分钟）
    08-I-03. Example (1/3) （3分钟）
    08-I-04. Example (2/3) （4分钟）
    08-I-05. Example (3/3) （5分钟）
    08-I-06. Query Time (1/3) （3分钟）
    08-I-07. Query Time (2/3) （3分钟）
    08-I-08. Query Time (3/3) （5分钟）
    08-J-01. General Windowing Query （7分钟）
    08-J-02. Elementary Interval （4分钟）
    08-J-03. Discretization （4分钟）
    08-J-04. Worst Case （3分钟）
    08-J-05. BBST （3分钟）
    08-J-06. Solving Stabbing Query （2分钟）
    08-J-07. Worst Case （3分钟）
    08-J-08. Common Ancestor （7分钟）
    08-J-09. Canonical Subsets （7分钟）
    08-J-10. O(nlogn) Space （3分钟）
    08-J-11. Constructing A Segment Tree （8分钟）
    08-J-12. Inserting A Segment (1) （3分钟）
    08-J-13. Inserting A Segment (2) （4分钟）
    08-J-14. Inserting A Segment (3) （3分钟）
    08-J-15. Query Algorithm （6分钟）
    08-J-16. Query Time （3分钟）
    08-K-01. Review （2分钟）
    08-K-02. X-Segment Tree （6分钟）
    08-K-03. Associative Structure （3分钟）
    08-K-04. Vertical Segment Stabbing Query （2分钟）
    京ICP备20031688号 　|　 京公网安备 11011502004263 　 |　 教APP备1102393号
    友情链接
    常见问题
    关于我们
    联系方式
    北京工商大学嘉华学院——在线教学平台
    地址 : 北京通州宋庄南路甲一号
    网络中心电话：
    教务处电话：