当前课程知识点:计算几何 > 06. Point Location > G. Kirkpatrick Structure > 06-G-01. Optimal And Simpler
对于刚才我们介绍的
persistent structure
我相信你
肯定会印象深刻
因为它的技巧
太高明了
当然高明的东西
也会显得更加的复杂
某种意义上讲
也未必实用
实际上情况也是如此
我们不禁要问
这样一个问题
有没有更简单的方法
有没有更
方便的简明的实现
同样能够在刚才所说的
那一系列最优的指标下
来完成point location这个问题呢
在这个问题的发展历史上
Kirkpatrick
是一个非常重要的人物
因为他提出的
一个专门的一个几何结构
就可以做到这样
我们将会看到
Kirkpatrick
所提出的这样的一个几何结构
是一个分层次的结构
它从上到下
由粗到精
描述了我们所要做点定位的
那个原始的subdivision
实际上查找过程也是如此
每次都是从顶上出发
然后
基于一个相对粗糙一点的模型
先做一个定位
将搜索的范围
锁定到一个相对小的范围
然后呢
在进一步的
进到下一个层次
再做一次搜索
又往深入的方向
再前进一步
将查找的范围
再次搜索到更小的一个范围
如此不断的下行 下行
直到最终
达到最精细的那个subdivision
从而给出正确的答案
所以这样的一个过程
整个从方法论的角度讲
我们也可以概括为
叫做由粗到细
不断的
依然是
简而治之
-Before we start
--html
-Evaluation
--html
-Online Judge
--html
-Lecture notes
--html
-Discussion
--html
-A. History of This Course
--00-A. History of This Course
-B. What's Computational Geometry
--00-B. What's Computational Geometry
-B. What's Computational Geometry--作业
-C. How to Learn CG Better
--00-C. How to Learn CG Better
-C. How to Learn CG Better--作业
-D. Why English
-A. Convexity
-A. Convexity--作业
-B. Extreme Points
-B. Extreme Points--作业
-C. Extreme Edges
-C. Extreme Edges--作业
-D. Incremental Construction
--01-D-01. Decrease and Conquer
--01-D-02. In-Convex-Polygon Test
--01-D-03. Why Not Binary Search
-D. Incremental Construction--作业
-E. Jarvis March
--01-E-06. Lowest-Then-Leftmost
-E. Jarvis March--作业
-F. Lower Bound
--01-F-02. CAO Chong's Methodology
-F. Lower Bound--作业
-G. Graham Scan: Algorithm
-G. Graham Scan: Algorithm--作业
-H. Graham Scan: Example
-H. Graham Scan: Example--作业
-I. Graham Scan: Correctness
-I. Graham Scan: Correctness--作业
-J. Graham Scan: Analysis
-J. Graham Scan: Analysis--作业
-K. Divide-And-Conquer (1)
-K. Divide-And-Conquer (1)--作业
-L. Divide-And-Conquer (2)
--01-L-03. Topmost + Bottommost ?
--01-L-07. More Considerations
-L. Divide-And-Conquer (2)--作业
-M. Wrap-Up
-0. Introduction
-0. Introduction--作业
-A. Preliminary
-A. Preliminary--作业
-B. Interval Intersection Detection
-B. Interval Intersection Detection--作业
-C. Segment Intersection Reporting
-C. Segment Intersection Reporting--作业
-D. BO Algorithm: Strategy
--02-D-01. Proximity & Separability
--02-D-02. Comparability & Ordering
-D. BO Algorithm: Strategy--作业
-E. BO Algorithm: Implementation
--02-E-03. Events & Operations
-E. BO Algorithm: Implementation--作业
-F. BO Algorithm: Analysis
--02-F-04. Complexity of Event Queue
--02-F-05. Complexity of Status Structure
-F. BO Algorithm: Analysis--作业
-G. Convex Polygon Intersection Detection
--02-G-01. Problem Specification
--02-G-02. Monotone Partitioning
--02-G-04. Decrease-And-Conquer
-G. Convex Polygon Intersection Detection--作业
-H. Edge Chasing
--02-H-01. Eliminating Sickles
-H. Edge Chasing--作业
-I. Plane Sweeping
-I. Plane Sweeping--作业
-J. Halfplane Intersection Construction
-J. Halfplane Intersection Construction--作业
-0. Methodology
-0. Methodology--作业
-A. Art Gallery Problem
--03-A-02. Lower & Upper Bounds
--03-A-04. Approximation & Classification
-A. Art Gallery Problem--作业
-B. Art Gallery Theorem
--03-B-01. Necessity of floor(n/3)
--03-B-02. Sufficiency by Fan Decomposition
-B. Art Gallery Theorem--作业
-C. Fisk's Proof
--03-C-04. Pigeon-Hole Principle
-C. Fisk's Proof--作业
-D. Orthogonal Polygons
--03-D-01. Necessity of floor(n/4)
--03-D-02. Sufficiency by Convex Quadrilateralization
-D. Orthogonal Polygons--作业
-E. Triangulation
-E. Triangulation--作业
-F. Triangulating Monotone Polygons
--03-F-02. Monotonicity Testing
--03-F-04. Stack-Chain Consistency
-F. Triangulating Monotone Polygons--作业
-G. Monotone Decomposition
-G. Monotone Decomposition--作业
-I. Tetrahedralization
--03-I-01. Polyhedron Decomposition
--03-I-02. Schonhardt's Polyhedron
-I. Tetrahedralization--作业
-A. Introduction
--04-A-02. Dining Halls on Campus
--04-A-03. More Analogies & Applications
-A. Introduction--作业
-B. Terminologies
--04-B-02. Intersecting Halfspaces
--04-B-04. Planar Voronoi Diagram
-B. Terminologies--作业
-C. Properties
--04-C-03. Nearest = Concyclic
--04-C-04. Number of Nearest Sites = Degree
-C. Properties--作业
-D. Complexity
-D. Complexity--作业
-E. Representation
-E. Representation--作业
-F. DCEL
-F. DCEL--作业
-G. Hardness
--04-G-03. Voronoi Diagram In General Position
-G. Hardness--作业
-H. Sorted Sets
--04-H-01. Convex Hull Made Easier
--04-H-02. Convex Hull As A Combinatorial Structure
--04-H-03. Voronoi Diagram As A Geometric Structure
-H. Sorted Sets--作业
-I. VD_sorted
--04-I-06. Sorting Not Made Easier
-I. VD_sorted--作业
-J. Naive Construction
-J. Naive Construction--作业
-K. Incremental Construction
-K. Incremental Construction--作业
-L. Divide-And-Conquer
--04-L-09. Intersecting with Cells
-L. Divide-And-Conquer--作业
-M. Plane-Sweep
--04-M-09. Circle Event: What, When & Where
-M. Plane-Sweep--作业
-A. Point Set Triangulation
-A. Point Set Triangulation--作业
-B. Delaunay Triangulation
-B. Delaunay Triangulation--作业
-C. Properties
-C. Properties--作业
-D. Proximity Graph
--05-D-02. Relative Neighborhood Graph
-D. Proximity Graph--作业
-E. Euclidean Minimum Spanning Tree
-E. Euclidean Minimum Spanning Tree--作业
-F. Euclidean Traveling Salesman Problem
-G. Minimum Weighted Triangulation
-G. Minimum Weighted Triangulation--作业
-H. Construction
--05-H-03. Maximizing The Minimum Angle
--05-H-04. Evolution By Edge Flipping
-H. Construction--作业
-I. RIC With Example
-I. RIC With Example--作业
-J. Randomized Incremental Construction
--05-J-01. Recursive Implementation
--05-J-02. Iterative Implementation
-J. Randomized Incremental Construction--作业
-K. RIC Analysis
--05-K-04. Types Of Edge Change
--05-K-05. Number Of Edge Changes
--05-K-07. Number Of Rebucketings
--05-K-08. Probability For Rebucketing
--05-K-10. Further Consideration
-0. Online/Offline Algorithms
--06-0. Online/Offline Algorithms
-0. Online/Offline Algorithms--作业
-A. Introduction
--06-A-03. Assumptions For Clarity
--06-A-05. Performance Measurements
-A. Introduction--作业
-B. Slab Method
--06-B-02. Ordering Trapezoids
-B. Slab Method--作业
-C. Persistence
--06-C-01. Ephemeral Structure
--06-C-02. Persistent Structure
-C. Persistence--作业
-D. Path Copying
--06-D-03. Storage Optimization
-D. Path Copying--作业
-E. Node Copying
-E. Node Copying--作业
-F. Limited Node Copying
-G. Kirkpatrick Structure
--06-G-01. Optimal And Simpler
--06-G-06. The More The Better
--06-G-07. The Fewer The Better
--06-G-09. Existence Of Independent Subset
--06-G-10. Construction Of Independent Subset
-G. Kirkpatrick Structure--作业
-H. Trapezoidal Map
--06-H-03. Properties & Complexity
--06-H-04. Search Structure: Example
--06-H-05. Search Structure: Nodes
--06-H-06. Search Structure: Performance
-H. Trapezoidal Map--作业
-I. Constructing Trapezoidal Map
--06-I-04. Case 1: Two Endpoints
--06-I-05. Case 2: One Endpoint
--06-I-06. Case 3: No Endpoints
-J. Performance Of Trapezoidal Map
--06-J-03. Number Of Ray Trimmed
--06-J-04. Number Of Trapezoidals Created (1)
--06-J-05. Number Of Trapezoidals Created (2)
--06-J-06. Time For Point Location
--06-J-07. Size Of Search Structure
--06-J-08. Fixed Query Point + Randomly Created Maps
--06-J-10. Probability Of Enclosing Trapezoid Changed
-A. Range Query
--07-A-01. 1-Dimensional Range Query
-A. Range Query--作业
-B. BBST
--07-B-02. Lowest Common Ancestor
-B. BBST--作业
-C. kd-Tree: Structure
-C. kd-Tree: Structure--作业
-D. kd-Tree: Algorithm
-D. kd-Tree: Algorithm--作业
-E. kd-Tree: Performance
--07-E-01. Preprocessing Time + Storage
-E. kd-Tree: Performance--作业
-F. Range Tree: Structure
--07-F-03. x-Query * y-Queries
-F. Range Tree: Structure--作业
-G. Range Tree: Query
-G. Range Tree: Query--作业
-H. Range Tree: Performance
-H. Range Tree: Performance--作业
-I. Range Tree: Optimization
--07-I-04. Fractional Cascading
-A. Orthogonal Windowing Query
-A. Orthogonal Windowing Query--作业
-B. Stabbing Query
-C. Interval Tree: Construction
-C. Interval Tree: Construction--作业
-D. Interval Tree: Query
-D. Interval Tree: Query--作业
-E. Stabbing With A Segment
--08-E-03. Query Algorithm (1)
--08-E-04. Query Algorithm (2)
-F. Grounded Range Query
--08-F-03. 1D-GRQ Using Range Tree
--08-F-04. 1D-GRQ By Linear Scan
-G. 1D-GRQ Using Heap
-G. 1D-GRQ Using Heap--作业
-H. Priority Search Tree
--08-H-03. Sibling Partitioning
-H. Priority Search Tree--作业
-I. 2D-GRQ Using PST
-I. 2D-GRQ Using PST--作业
-J. Segment Tree
--08-J-01. General Windowing Query
--08-J-02. Elementary Interval
--08-J-06. Solving Stabbing Query
--08-J-11. Constructing A Segment Tree
--08-J-12. Inserting A Segment (1)
--08-J-13. Inserting A Segment (2)
--08-J-14. Inserting A Segment (3)
-K. Vertical Segment Stabbing Query