当前课程知识点:计算几何 >  06. Point Location >  A. Introduction >  06-A-03. Assumptions For Clarity

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

06-A-03. Assumptions For Clarity在线视频

06-A-03. Assumptions For Clarity

下一节:06-A-04. Input Size

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

06-A-03. Assumptions For Clarity课程教案、知识点、字幕

在做过了这样的抽象和简化之后

我们当然最终是要来报告

你所带查询的那些点

到底是落在哪个face里头

但是我们的算法

其实并不知道你确切的

每张face代表什么语义

对它来说

每一张face只是一个抽象的实体

为此

我们需要为这样的每一个抽象的实体

来做一个标识

具体来讲

我们要给每一张面都做一个标记

当然如果你还记得

邓老师在数据结构课上

所引用的一句名言

也就是所有的世界上万世万物

无非都是数字

你就很自然能够想像到

我们最简单不过的

最直接的一个标记的方法

就是给每一张面

赋予一个整数

比如1号 2号 3号一直到100

二万 三百万等等等等

做一个标号

那么一旦我们在任何时候

需要做这么一次查询

并且算法得到了这么样一个

相应的结果

它所要做的事情

在我们这里的约定

无非就是返回这张face的编号

我们说在数学上

这件事已经足以达到

我们刚才所提的那种算法的需要了

那么从具体的数据结构来说

我们为了支持更高效的这种查找

我们不妨采用我们此前

已经研究并且使用多次的那种数据结构

也就是DCEL

如果你对这个有点淡忘

不妨温习一下

我们前面所讲过的相关的知识

当然我们这里要回避掉

很多很讨厌的情况

比如说各种各样的退化情况

这个有可能在原始的subdivision中

就会存在

那么这里我们也假设

它们不在我们的讨论范围之内

还有一个就是在我们事后

每次的这个range query的时候

所有的query points

也本身有可能有歧义

试想一下

如果有一个query point

正好落在某一条边上

甚至可能恰好落在多条边的汇聚点上

这个时候

刚才我们说的这个算法

到底应该返回哪张面

我们说这是有歧义的

作为老师来说

非常幸运

因为我们有特权说

我们不考虑这些问题

确实在接下来的讨论中

我们不考虑这些问题

但是这并不意味着

你可以不讨论这些问题

因为你必须在实际运用中

把这个算法变成一个可用的

鲁棒的真正的程序

而这件事是需要通过你自己的努力的

老师并不能帮助你

至少不能直接的帮助你

计算几何课程列表:

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-A-03. Assumptions For Clarity笔记与讨论

也许你还感兴趣的课程:

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