当前课程知识点:计算几何 >  01. Convex Hull >  C. Extreme Edges >  01-C-01. Definition

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

01-C-01. Definition在线视频

01-C-01. Definition

下一节:01-C-02. Algorithm

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

01-C-01. Definition课程教案、知识点、字幕

好 刚才我们已经得到了

一个完整的基于极点的

这样的原理的凸包构造算法

然而,我们并不能就此满意

因为刚才我们看到了

它的复杂度高达n^4

接下来,我们试图从另一个角度

来对它做改进

那么我们的改进

要依然地延续刚才极点的思路

我们要将这个概念

推广到边引入所谓的极边

那么什么叫做极边呢

我们说极边的候选者

其实就是来自于点集中

任何两个点之间的联边

任何两个点确实都有一条联边

但是有的能够称作是极边

有的不是

你已经看出来了——我相信

没错

凡是对最终的凸包

有贡献的那些边

我们都称之为极边

凡是那些对凸包没有贡献的

比如这两个点之间

我们没有画出来的那条边

就不是极边

或者叫做非极边,non-extreme Edge

那么同样我们要运用自己的眼睛

来观察一下

极边亦或非极边

二者之间到底有什么本质的差异呢

这种差异需要能够帮助我们

可以操作性地来甄别它们

我想你也大概有想法了

是的

就像我们刚才定义极点一样

我们说如果有一条

这样的联边

确实是极边的话

与刚才类似

那么所有的点

都会同时落在它的同侧

当然相应地,另一侧

就必然是空的

如果还是沿用

我们刚才那个逆时针

那样的次序的话

我们就会发现

凸包边界上的

所有的每一条边

都有这样的一个特性

也就是所有的点

都恰好落在它的左侧

对这个是这样

对这个也是这样

对这个以及所有的极边

都是落在左侧

或者反过来说

它们的右侧都是空的

当然

作为这个充要条件的

另一个方向

你需要反过来验证一下

除此之外的联边都不是极边

无论它们是联接于两个非极点之间

还是联接于一个极点

和一个非极点之间

甚至它们是联接于两个极点之间

但是这两个极点 都并非是相邻的

凡此种种

你都需要验证一下

它(们)确实不具有刚才的那个特性

也就是它们至少有一侧是空的

这些工作都留给你在课后完成

在这里我们不妨把它

当做是一个成立的结论

并且作为我们接下来

判定和构造算法的依据

这样我们算法中的实质问题

就自然地转化

和具体化为如何来甄别

任何两个点之间的那条联边

是否为极边的问题

计算几何课程列表:

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

01-C-01. Definition笔记与讨论

也许你还感兴趣的课程:

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