当前课程知识点:计算几何 >  06. Point Location >  J. Performance Of Trapezoidal Map >  06-J-05. Number Of Trapezoidals Created (2)

返回《计算几何》慕课在线视频课程列表

06-J-05. Number Of Trapezoidals Created (2)在线视频

06-J-05. Number Of Trapezoidals Created (2)

下一节:06-J-06. Time For Point Location

返回《计算几何》慕课在线视频列表

06-J-05. Number Of Trapezoidals Created (2)课程教案、知识点、字幕

我们现在就将目光固定在

一个特定的梯形Δ上

我们来看看这个梯形的生成

会有哪些线段的插入而造成的

我们说

仔细观察无非四种情况

哪四种情况呢

也就是最新插入的那条线段s

有可能是这条

也就是它的顶边

如果是这样

它确实会被生成出来

还有可能对称的

如果是它的底边

第二种情况

第三种情况

没错也就是它的左边

这条边的插入

因为它的右端点

所以构成了这个新的梯形的左边界

所以它的插入

也会导致这个梯形的生成

当然对称的还有第四种情况

也就是如果是最后插入的那条线段

是这条边

那么也会导致Δ的生成

好了这四条边中间的任何一条边

是最后一条边插入的

都会导致这个梯形

在刚刚过去的

最后那次迭代中被生成出来

你需要再说服一下自己的就是

除此之外

其他边作为最后一条边的插入

确实不会导致这个梯形的生成

这说明什么呢

这就意味着

刚才我们那个嵌套在内部的

求和号其实它的数值

就应该不会大于4

一个常数

如果我们将它替换掉

刚才的内部求和号的话

我们就会发现

那个求和号就变成了这样一个

非常简明的形式

这个简明的形式确实已经简明到

我们能够一眼看到的地步

因为这里无非就是对

当前这个梯形图中的所有的梯形

来做一个求和

每一个数值具体的都是4

所以我们只要把其中那个数字

呈出来就可以了

我们此前曾经讲过

如果当前已经插入的

线段的数目是i的话

那么其中的边 面

当然也包括梯形

其中的数目都应该不会超过O(i)

所以的话

我们马上就会得出结论

我们刚才所要计算的这个期望值

经过一系列的推导

它恰好就是常数

正如我们刚才所声称的那样

这样的话我们就证明了

在整个的这个迭代式的

递增式的这个算法过程中

每一步迭代中

从期望的角度来看

消耗于新的梯形的生成方面

所需要的时间居然都是常数

而我们知道期望值是满足线性率的

纵观整个这个算法的过程

它消耗在这上面的时间

自然也就是每一步的

这个时间的总和

而总体的期望值也应该等于

每一步的期望值的总和

我们刚刚证明过

每一步的期望值都是常数

所以我们很自然就可以得出结论

整个这个算法过程中

消耗于生成这些梯形的时间

累计不过线性

我们当然有预测

总体的时间应该是不超过O(nlogn)

而相对于线性来说

O(nlogn)是很大的

而相对于O(nlogn)来说

这个线性其实是可以忽略掉的

这说明什么呢

这也说明

我们整个的构造算法的时间

实质上讲

主体上讲

是应该消耗于我们的第一步

也就是点定位

刚才我们称作为t(i)的那个时间

计算几何课程列表:

00. Introduction

-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

--00-D. Why English

01. Convex Hull

-A. Convexity

--01-A-01. Why Convex Hull

--01-A-02. Nails In The Table

--01-A-03. Paint Blending

--01-A-04. Color Space

--01-A-05. Convex Hull

-A. Convexity--作业

-B. Extreme Points

--01-B-01. Extremity

--01-B-02. Strategy

--01-B-03. In-Triangle Test

--01-B-04. To-Left Test

--01-B-05. Determinant

-B. Extreme Points--作业

-C. Extreme Edges

--01-C-01. Definition

--01-C-02. Algorithm

--01-C-03. Demonstration

-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

--01-D-04. Support-Lines

--01-D-05. Pattern Of Turns

--01-D-06. Exterior/Interior

-D. Incremental Construction--作业

-E. Jarvis March

--01-E-01. Selectionsort

--01-E-02. Strategy

--01-E-03. Coherence

--01-E-04. To-Left Test

--01-E-05. Degeneracy

--01-E-06. Lowest-Then-Leftmost

--01-E-07. Implementation

--01-E-08. Output Sensitivity

-E. Jarvis March--作业

-F. Lower Bound

--01-F-01. Reduction

--01-F-02. CAO Chong's Methodology

--01-F-03. Transitivity

--01-F-04. Reduction: Input

--01-F-05. Reduction: Output

--01-F-06. Sorting ≤_N 2d-CH

-F. Lower Bound--作业

-G. Graham Scan: Algorithm

--01-G-01. Preprocessing

--01-G-02. Scan

--01-G-03. Simplest Cases

-G. Graham Scan: Algorithm--作业

-H. Graham Scan: Example

--01-H-01. Example (1/2)

--01-H-02. Example (2/2)

-H. Graham Scan: Example--作业

-I. Graham Scan: Correctness

--01-I-01. Left Turn

--01-I-02. Right Turn

--01-I-03. Presorting

-I. Graham Scan: Correctness--作业

-J. Graham Scan: Analysis

--01-J-01. Ω(n) Backtracks

--01-J-02. Planarity

--01-J-03. Amortization

--01-J-04. Simplification

-J. Graham Scan: Analysis--作业

-K. Divide-And-Conquer (1)

--01-K-01. Merge

--01-K-02. Common Kernel

--01-K-03. Interior

--01-K-04. Exterior

-K. Divide-And-Conquer (1)--作业

-L. Divide-And-Conquer (2)

--01-L-01. Preprocessing

--01-L-02. Common Tangents

--01-L-03. Topmost + Bottommost ?

--01-L-04. Stitch

--01-L-05. Zig-Zag

--01-L-06. Time Cost

--01-L-07. More Considerations

-L. Divide-And-Conquer (2)--作业

-M. Wrap-Up

--01-M. Wrap-Up

02. Geometric Intersection

-0. Introduction

--02-0. Introduction

-0. Introduction--作业

-A. Preliminary

--02-A-01. EU

--02-A-02. Min-Gap

--02-A-03. Max-Gap

--02-A-04. IEU

-A. Preliminary--作业

-B. Interval Intersection Detection

--02-B-01. Algorithm

--02-B-02. Lower Bound

-B. Interval Intersection Detection--作业

-C. Segment Intersection Reporting

--02-C-01. Brute-force

--02-C-02. Hardness

-C. Segment Intersection Reporting--作业

-D. BO Algorithm: Strategy

--02-D-01. Proximity & Separability

--02-D-02. Comparability & Ordering

--02-D-03. Data Structures

--02-D-04. Possible Cases

-D. BO Algorithm: Strategy--作业

-E. BO Algorithm: Implementation

--02-E-01. Degeneracy

--02-E-02. Event Queue

--02-E-03. Events & Operations

--02-E-04. Sweepline Status

-E. BO Algorithm: Implementation--作业

-F. BO Algorithm: Analysis

--02-F-01. Correctness

--02-F-02. Example

--02-F-03. Retesting

--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-03. Criterion

--02-G-04. Decrease-And-Conquer

--02-G-05. Example Cases

--02-G-06. Complexity

-G. Convex Polygon Intersection Detection--作业

-H. Edge Chasing

--02-H-01. Eliminating Sickles

--02-H-02. Example

--02-H-03. Analysis

-H. Edge Chasing--作业

-I. Plane Sweeping

--02-I. Plane Sweeping

-I. Plane Sweeping--作业

-J. Halfplane Intersection Construction

--02-J-01. The Problem

--02-J-02. Lower Bound

--02-J-03. Divide-And-Conquer

-J. Halfplane Intersection Construction--作业

03. Triangulation

-0. Methodology

--03-0. Methodology

-0. Methodology--作业

-A. Art Gallery Problem

--03-A-01. Definition

--03-A-02. Lower & Upper Bounds

--03-A-03. Hardness

--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-01. Triangulation

--03-C-02. 3-Coloring

--03-C-03. Domination

--03-C-04. Pigeon-Hole Principle

--03-C-05. Generalization

-C. Fisk's Proof--作业

-D. Orthogonal Polygons

--03-D-01. Necessity of floor(n/4)

--03-D-02. Sufficiency by Convex Quadrilateralization

--03-D-03. Generalization

-D. Orthogonal Polygons--作业

-E. Triangulation

--03-E-01. Existence

--03-E-02. Ear & Mouth

--03-E-03. Two-Ear Theorem

--03-E-04. Well-Order

--03-E-05. Ear Candidate

--03-E-06. Induction

--03-E-07. Well-Order (Again)

--03-E-08. Properties

-E. Triangulation--作业

-F. Triangulating Monotone Polygons

--03-F-01. Monotone Polygon

--03-F-02. Monotonicity Testing

--03-F-03. Strategy

--03-F-04. Stack-Chain Consistency

--03-F-05. Same Side + Reflex

--03-F-06. Same Side + Convex

--03-F-07. Opposite Side

--03-F-08. Example

--03-F-09. Analysis

-F. Triangulating Monotone Polygons--作业

-G. Monotone Decomposition

--03-G-01. Cusps

--03-G-02. Helper

--03-G-03. Helper Candidate

--03-G-04. Sweep-Line Status

--03-G-05. Possible Cases

--03-G-06. Example

--03-G-07. Analysis

-G. Monotone Decomposition--作业

-I. Tetrahedralization

--03-I-01. Polyhedron Decomposition

--03-I-02. Schonhardt's Polyhedron

--03-I-03. Seidel's Polygon

-I. Tetrahedralization--作业

04. Voronoi Diagram

-A. Introduction

--04-A-01. A First Glance

--04-A-02. Dining Halls on Campus

--04-A-03. More Analogies & Applications

--04-A-04. Voronoi

-A. Introduction--作业

-B. Terminologies

--04-B-01. Site & Cell

--04-B-02. Intersecting Halfspaces

--04-B-03. Voronoi Diagram

--04-B-04. Planar Voronoi Diagram

-B. Terminologies--作业

-C. Properties

--04-C-01. Non-Empty Cells

--04-C-02. Empty Disks

--04-C-03. Nearest = Concyclic

--04-C-04. Number of Nearest Sites = Degree

--04-C-05. Split & Merge

-C. Properties--作业

-D. Complexity

--04-D-01. Linearity

--04-D-02. Proof

-D. Complexity--作业

-E. Representation

--04-E-01. Subdivision

--04-E-02. Fary's Theorem

--04-E-03. Representing VD

-E. Representation--作业

-F. DCEL

--04-F-01. Twin Edges

--04-F-02. Half-Edge

--04-F-03. Vertex & Face

--04-F-04. Traversal

--04-F-05. True Or False

--04-F-06. Application

-F. DCEL--作业

-G. Hardness

--04-G-01. 1D Voronoi Diagram

--04-G-02. 2D Voronoi Diagram

--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-01. ε-Closeness

--04-I-02. Lifting

--04-I-03. Projection

--04-I-04. Case A

--04-I-05. Case B

--04-I-06. Sorting Not Made Easier

-I. VD_sorted--作业

-J. Naive Construction

--J. Naive Construction

-J. Naive Construction--作业

-K. Incremental Construction

--04-K-01. Royal Garden

--04-K-02. Disjoint Union

--04-K-03. Complexity

-K. Incremental Construction--作业

-L. Divide-And-Conquer

--04-L-01. Strategy

--04-L-02. Solving Overlaps

--04-L-03. Contour

--04-L-04. Bisectors

--04-L-05. Y-Monotonicity

--04-L-06. Common Tangents

--04-L-07. Contour Length

--04-L-08. Clip & Stitch

--04-L-09. Intersecting with Cells

--04-L-10. Convexity

--04-L-11. Avoiding Rescans

-L. Divide-And-Conquer--作业

-M. Plane-Sweep

--04-M-01. A First Glance

--04-M-02. Backtracking

--04-M-03. Fortune's Trick

--04-M-04. Frozen Region

--04-M-05. Beach Line

--04-M-06. Lower Envelope

--04-M-07. Break Points

--04-M-08. Events

--04-M-09. Circle Event: What, When & Where

--04-M-10. Circle Event: Why

--04-M-11. Circle Event: How

--04-M-12. Site Event: What

--04-M-13. Site Event: How

-M. Plane-Sweep--作业

05. Delaunay Triangulation

-A. Point Set Triangulation

--05-A-01. Definition

--05-A-02. Edge Flipping

--05-A-03. Upper Bound

--05-A-04. Lower Bound

-A. Point Set Triangulation--作业

-B. Delaunay Triangulation

--05-B-01. Dual Graph

--05-B-02. Triangulation

--05-B-03. Hardness

--05-B-04. History

-B. Delaunay Triangulation--作业

-C. Properties

--05-C-01. Empty Circumcircle

--05-C-02. Empty Circle

--05-C-03. Nearest Neighbor

--05-C-04. Complexity

-C. Properties--作业

-D. Proximity Graph

--05-D-01. Gabriel Graph

--05-D-02. Relative Neighborhood Graph

--05-D-03. Lower Bounds

-D. Proximity Graph--作业

-E. Euclidean Minimum Spanning Tree

--05-E-01. Definition

--05-E-02. Construction

--05-E-03. Subgraph of RNG

--05-E-04. Example

-E. Euclidean Minimum Spanning Tree--作业

-F. Euclidean Traveling Salesman Problem

--05-F-01. Definition

--05-F-02. NP-Hardness

--05-F-03. Approximation

-G. Minimum Weighted Triangulation

--05-G-01. Definition

--05-G-02. Counter-Example

--05-G-03. Hardness

-G. Minimum Weighted Triangulation--作业

-H. Construction

--05-H-01. Subtended Arc

--05-H-02. Angle Vector

--05-H-03. Maximizing The Minimum Angle

--05-H-04. Evolution By Edge Flipping

--05-H-05. Strategies

-H. Construction--作业

-I. RIC With Example

--05-I-01. Idea

--05-I-02. Point Location

--05-I-03. In-Circle Test

--05-I-04. Edge Flipping

--05-I-05. Frontier

--05-I-06. Convergence

-I. RIC With Example--作业

-J. Randomized Incremental Construction

--05-J-01. Recursive Implementation

--05-J-02. Iterative Implementation

--05-J-03. In-Circle Test

--05-J-04. Point Location

-J. Randomized Incremental Construction--作业

-K. RIC Analysis

--05-K-01. Time Cost

--05-K-02. Backward Analysis

--05-K-03. Preconditions

--05-K-04. Types Of Edge Change

--05-K-05. Number Of Edge Changes

--05-K-06. Average Degree

--05-K-07. Number Of Rebucketings

--05-K-08. Probability For Rebucketing

--05-K-09. Expectation

--05-K-10. Further Consideration

06. Point Location

-0. Online/Offline Algorithms

--06-0. Online/Offline Algorithms

-0. Online/Offline Algorithms--作业

-A. Introduction

--06-A-01. Where Am I

--06-A-02. Point Location

--06-A-03. Assumptions For Clarity

--06-A-04. Input Size

--06-A-05. Performance Measurements

--06-A-06. A Global View

-A. Introduction--作业

-B. Slab Method

--06-B-01. Slab Decomposition

--06-B-02. Ordering Trapezoids

--06-B-03. Tree of Trees

--06-B-04. Example

--06-B-05. Query Time

--06-B-06. Preprocessing Time

--06-B-07. Storage Cost

--06-B-08. Worst Case

-B. Slab Method--作业

-C. Persistence

--06-C-01. Ephemeral Structure

--06-C-02. Persistent Structure

--06-C-03. Persistent Slabs

-C. Persistence--作业

-D. Path Copying

--06-D-01. Strategy

--06-D-02. X-Search

--06-D-03. Storage Optimization

-D. Path Copying--作业

-E. Node Copying

--06-E-01. O(1) Rotation

--06-E-02. Strategy

--06-E-03. Why Red-Black

--06-E-04. Linear Space

--06-E-05. Time Penalty

-E. Node Copying--作业

-F. Limited Node Copying

--06-F-01. Idea

--06-F-02. Split

--06-F-03. Complexity

--06-F-04. Recoloring

-G. Kirkpatrick Structure

--06-G-01. Optimal And Simpler

--06-G-02. Triangulation

--06-G-03. Example

--06-G-04. Hierarchy

--06-G-05. Independent Subset

--06-G-06. The More The Better

--06-G-07. The Fewer The Better

--06-G-08. Degree

--06-G-09. Existence Of Independent Subset

--06-G-10. Construction Of Independent Subset

--06-G-11. DAG

-G. Kirkpatrick Structure--作业

-H. Trapezoidal Map

--06-H-01. Ray Shooting

--06-H-02. Decomposition

--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-01. Initialization

--06-I-02. Iteration

--06-I-03. Challenges

--06-I-04. Case 1: Two Endpoints

--06-I-05. Case 2: One Endpoint

--06-I-06. Case 3: No Endpoints

--06-I-07. Example

-J. Performance Of Trapezoidal Map

--06-J-01. Randomization

--06-J-02. Expectation

--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-09. Each Single Step

--06-J-10. Probability Of Enclosing Trapezoid Changed

--06-J-11. Query Time

07. Geometric Range Search

-A. Range Query

--07-A-01. 1-Dimensional Range Query

--07-A-02. Brute-force

--07-A-03. Binary Search

--07-A-04. Output Sensitivity

--07-A-05. Planar Range Query

-A. Range Query--作业

-B. BBST

--07-B-01. Structure

--07-B-02. Lowest Common Ancestor

--07-B-03. Query Algorithm

--07-B-04. Complexity (1)

--07-B-05. Complexity (2)

-B. BBST--作业

-C. kd-Tree: Structure

--07-C-01. 2d-Tree

--07-C-02. Example

--07-C-03. Construction

--07-C-04. Example

--07-C-05. Canonical Subsets

-C. kd-Tree: Structure--作业

-D. kd-Tree: Algorithm

--07-D-01. Query

--07-D-02. Example

--07-D-03. Optimization

-D. kd-Tree: Algorithm--作业

-E. kd-Tree: Performance

--07-E-01. Preprocessing Time + Storage

--07-E-02. Query Time

--07-E-03. Beyond 2D

-E. kd-Tree: Performance--作业

-F. Range Tree: Structure

--07-F-01. x-Query + y-Query

--07-F-02. Worst Case

--07-F-03. x-Query * y-Queries

-F. Range Tree: Structure--作业

-G. Range Tree: Query

--07-G-01. Painters' Strategy

--07-G-02. X-Tree

--07-G-03. Y-Trees

--07-G-04. Algorithm

-G. Range Tree: Query--作业

-H. Range Tree: Performance

--07-H-01. Storage

--07-H-02. Preprocessing Time

--07-H-03. Query Time

--07-H-04. Beyond 2D

-H. Range Tree: Performance--作业

-I. Range Tree: Optimization

--07-I-01. Y-Lists

--07-I-02. Coherence

--07-I-03. Idea

--07-I-04. Fractional Cascading

--07-I-05. Complexity

08. Windowing Query

-A. Orthogonal Windowing Query

--08-A-01. Definition

--08-A-02. Classification

-A. Orthogonal Windowing Query--作业

-B. Stabbing Query

--08-B-01. 1D Windowing Query

--08-B-02. Stabbing Query

-C. Interval Tree: Construction

--08-C-01. Median

--08-C-02. Partitioning

--08-C-03. Balance

--08-C-04. Associative Lists

--08-C-05. Complexity

-C. Interval Tree: Construction--作业

-D. Interval Tree: Query

--08-D-01. Algorithm (1)

--08-D-02. Algorithm (2)

--08-D-03. Complexity

-D. Interval Tree: Query--作业

-E. Stabbing With A Segment

--08-E-01. Definition

--08-E-02. Interval Tree

--08-E-03. Query Algorithm (1)

--08-E-04. Query Algorithm (2)

--08-E-05. Overview

--08-E-06. Complexity

-F. Grounded Range Query

--08-F-01. O(n) Space

--08-F-02. 2D-GRQ

--08-F-03. 1D-GRQ Using Range Tree

--08-F-04. 1D-GRQ By Linear Scan

-G. 1D-GRQ Using Heap

--08-G-01. Heap

--08-G-02. Query

--08-G-03. Example

--08-G-04. Complexity

-G. 1D-GRQ Using Heap--作业

-H. Priority Search Tree

--08-H-01. PST = Heap + BBST

--08-H-02. Order Property

--08-H-03. Sibling Partitioning

--08-H-04. Construction

-H. Priority Search Tree--作业

-I. 2D-GRQ Using PST

--08-I-01. Algorithm (1/2)

--08-I-02. Algorithm (2/2)

--08-I-03. Example (1/3)

--08-I-04. Example (2/3)

--08-I-05. Example (3/3)

--08-I-06. Query Time (1/3)

--08-I-07. Query Time (2/3)

--08-I-08. Query Time (3/3)

-I. 2D-GRQ Using PST--作业

-J. Segment Tree

--08-J-01. General Windowing Query

--08-J-02. Elementary Interval

--08-J-03. Discretization

--08-J-04. Worst Case

--08-J-05. BBST

--08-J-06. Solving Stabbing Query

--08-J-07. Worst Case

--08-J-08. Common Ancestor

--08-J-09. Canonical Subsets

--08-J-10. O(nlogn) Space

--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)

--08-J-15. Query Algorithm

--08-J-16. Query Time

-K. Vertical Segment Stabbing Query

--08-K-01. Review

--08-K-02. X-Segment Tree

--08-K-03. Associative Structure

--08-K-04. Vertical Segment Stabbing Query

06-J-05. Number Of Trapezoidals Created (2)笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。