当前课程知识点:计算几何 >  03. Triangulation >  A. Art Gallery Problem >  03-A-01. Definition

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

03-A-01. Definition在线视频

03-A-01. Definition

下一节:03-A-02. Lower & Upper Bounds

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

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

好 实际上三角剖分

不仅是解决多边形很多问题的

一个基本的方法

而且在理论上

它首先也非常的有用

非常的有趣

我们这里就来看一个

非常有趣的一个例子

这个例子

也就是所谓的画廊问题

Art Gallery Problem

我们先来看一下

这个问题是怎么说的

我们都去过艺术画廊

艺术画廊从平面图来看

就可以抽象为是一个多边形

那么我们的艺术珍品

一般都会陈列在这个画廊中

那么现在来了

在我们川流不息的游客中

保不齐会有个别的窃贼

没错 窃贼

所以我们需要对这些艺术珍品

进行看护

怎么看护呢

白天可以通过人 保安

晚上呢

晚上我们不得不借用机器

机器的保安

那么最简单的形式

其实就是这种红色的点

所表示的那种摄像头

我们这里假设我们的摄像头是360°

都可以看到的

而且它们的视野范围

只要不受到墙壁的阻挡

是可以延伸到

任何足够远的距离

那么现在问题来了

对于任何的

这样一个给定的艺术画廊

我们最少需要用多少个摄像头

就足以将其中所有的艺术珍品

都看护起来

如果将这个问题

再进一步抽象的话

就是任意给定一个多边形P

如果我们要足以用一些点 哨兵

将它覆盖的话

那么这个点哨兵的集合X

它的基数最少能够达到多少

越少越优

这是我们所追求的目标

我们不妨就来看一下

这个具体的例子

我们首先可以假设

在这个位置放置一个哨兵

那么它所能覆盖的区域

自然也就是这部分

确认一下

我们会发现

尽管它看护了足够大的一个面积

但是毕竟还是有一部分遗漏掉了

怎么办

增加哨兵

我们在这个位置上

可以考虑再追加一个摄像头

两个摄像头

那么它所对应的看护的区域

就是这个

现在好了

在我们同时使用了

刚才这样两个摄像头之后

我们确实可以无一处遗漏的

将整个这个画廊都覆盖起来

那么我们用到了两个摄像头

按照原来这个问题最初的问法

这两个摄像头是不是有重复呢

或者等效的说

我们是不是可以

用更少的摄像头呢

敏锐的你肯定已经发现不行

因为你注意到

这里有两个角点

我们很容易验证

对于这两个角点来说

你是不可能通过同一个哨兵

同时将它们都看护起来

换句话说这个时候

我们不得不用至少两个摄像头

所以换句话说

对这个多边形来说

这已经是最优的解了

那么更一般的情况呢

计算几何课程列表:

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

03-A-01. Definition笔记与讨论

也许你还感兴趣的课程:

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