当前课程知识点:计算几何 >  08. Windowing Query >  J. Segment Tree >  08-J-12. Inserting A Segment (1)

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

08-J-12. Inserting A Segment (1)在线视频

08-J-12. Inserting A Segment (1)

下一节:08-J-13. Inserting A Segment (2)

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

08-J-12. Inserting A Segment (1)课程教案、知识点、字幕

那么我们就来看一下

这个算法的接口

也就是要将当前

我们待插入的一个区间s

一条线段插入到以v为树根的

一棵子树中

不要忘了

我们刚才的那个

是个贪心的策略

也就是说在自顶而下

你可以认为这样的

递归的过程中

一旦它能停下来

就立即停下来

记住这是一个原则

那么这里的贪心

一旦能够停下来这个原则

在这里指什么呢

其实兑现一下的话

发现很自然

就是说当前这个树根结点

所对应的那个EI

不要忘了

也就是它所支撑的

这个横向的范围

虽然很大

但是相对于待插入的这条线段

这个区间来说

还相形更小

以至于它完全的包含在其中

被后者覆盖

一旦是这种情况

这就是我们刚才那种贪心算法

能够生效的时刻

在这个时刻

我们就不要犹豫了

我们直接就将这个s

归入到刚才我们这个v

所对应的那个正则子集中

把它加到其中

就像刚才在这里

我们这样一条线段

在掉下来的时候

可能首先就会在这个位置

停留一次

并且在这个位置

相应的留下它的足迹

验证一下

算法在这个的时候

这个结点所对应的宽度

EI还很宽

以至于不能被红的包含

所以它什么都不做

在这个位置至少是这样

在接下来的这个区间

虽然它的长度已经比较短了

但是它至少在左侧

还多出一部分

没有落在这个红色

对应的那个范围之内

所以它也不是贪心这个原则

能够生效的时刻

首先能够生效的

第一个时刻

确实就是在这里

所以我们再看一下

这就是为什么

当这个馅饼掉下来的时候

首先会这个结点处

留下一个烙印

这是这种情况

那么我们需要说明的是

无论它确实是在这个地方

留下一个烙印

或者像刚才那些祖先那样

没有留下一个烙印

其实对它的后代来说

是没有影响的

它的后代

还需要独立的去做判断

计算几何课程列表:

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

08-J-12. Inserting A Segment (1)笔记与讨论

也许你还感兴趣的课程:

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