Part 4.


81 views
Uploaded on:
Category: Animals / Pets
Description
Part 4. The Gap and-Vanquish System. A Basic Sample. Finding the most extreme of a set S of n numbers . Time Intricacy. Time intricacy: Estimation of T(n): Accept n = 2 k , T(n) = 2T(n/2)+1 = 2(2T(n/4)+1)+1 = 4T(n/4)+2+1 : =2 k-1 T(2)+2 k-2 + … +4+2+1
Transcripts
Slide 1

Section 4 The Divide-and-Conquer Strategy

Slide 2

A Simple Example Finding the greatest of a set S of n numbers

Slide 3

Time Complexity Time intricacy: Calculation of T(n): Assume n = 2 k , T(n) = 2T(n/2)+1 = 2(2T(n/4)+1)+1 = 4T(n/4)+2+1 : =2 k-1 T(2)+2 k-2 + … +4+2+1 =2 k-1 +2 k-2 + … +4+2+1 =2 k - 1 = n-1

Slide 4

A General Divide-and-Conquer Algorithm Step 1 : If the issue size is little, tackle this issue straightforwardly; something else, split the first issue into 2 sub-issues with equivalent sizes. Step 2 : Recursively take care of these 2 sub-issues by applying this calculation. Step 3 : Merge the 2\'s arrangements sub-issues into a unique\'s answer issue.

Slide 5

Time Complexity of the General Algorithm Time many-sided quality: where S(n) : time for part M(n) : time for combining b : a steady c : a consistent

Slide 6

2-D Maxima Finding Problem Def : A point (x 1 , y 1 ) rules (x 2 , y 2 ) if x 1 > x 2 and y 1 > y 2 . A point is known as a maxima if no other point overwhelms it. Direct strategy : Compare each pair of focuses. Time multifaceted nature: O(n 2 )

Slide 7

Divide-and-Conquer for Maxima Finding The maximal purposes of S L and S R

Slide 8

The calculation: Input: A set S of n planar focuses. Yield: The maximal purposes of S. Step 1: If S contains one and only point, return it as the maxima. Something else, discover a line L opposite to the X-pivot which isolates S into S L and S R , with equivalent sizes. Step 2: Recursively locate the maximal purposes of S L and S R . Step 3: Find the biggest y-estimation of S R , meant as y R . Dispose of each of the maximal purposes of S L if its y-quality is not as much as y R .

Slide 9

Time intricacy: T(n) Step 1: O(n) Step 2: 2T(n/2) Step 3: O(n) Assume n = 2 k T(n) = O(n log n)

Slide 10

The Closest Pair Problem Given a set S of n focuses, discover a couple of focuses which are nearest together. 1-D rendition : Solved by sorting Time unpredictability : O(n log n)  2-D form

Slide 11

At most 6 focuses in territory A:

Slide 12

The calculation: Input: A set S of n planar focuses. Yield: The separation between two nearest focuses. Step 1: Sort indicates in S concurring their y-values. Step 2: If S contains stand out point, return vastness as its separation. Step 3: Find a middle line L opposite to the X-hub to gap S into S L and S R , with equivalent sizes. Step 4: Recursively apply Steps 2 and 3 to tackle the nearest match issues of S L and S R . Let d L (d R ) indicate the separation between the nearest combine in S L (S R ). Let d = min(d L , d R ).

Slide 13

Step 5: For a point P in the half-section limited by L-d and L, let its y-worth be meant as y P . For each such P, discover all focuses in the half-piece limited by L and L+d whose y-quality fall inside of y P +d and y P - d. In the event that the separation d  in the middle of P and a point in the other half-chunk is not as much as d, let d=d  . The last estimation of d is the answer. Time multifaceted nature: O(n log n) Step 1: O(n log n) Steps 2~5:  T(n) = O(n log n)

Slide 14

Concave polygon: Convex polygon: The Convex Hull Problem The raised body of an arrangement of planar focuses is the littlest arched polygon containing the focuses\' majority.

Slide 15

The gap and-overcome method to take care of the issue:

Slide 16

The combining technique: Select an inside point p. There are 3 successions of focuses which have expanding polar edges concerning p. (1) g, h, i, j, k (2) a, b, c, d (3) f, e Merge these 3 groupings into 1 succession: g, h, a, b, f, c, e, d, i, j, k. Apply Graham output to inspect the focuses one by one and take out the focuses which cause reflexive edges . (See the case on the following page.)

Slide 17

e.g. focuses b and f should be erased. Last result:

Slide 18

Divide-and-Conquer for Convex Hull Input : A set S of planar focuses Output : A curved body for S Step 1: If S contains close to five focuses, use thorough seeking to locate the arched frame and return. Step 2: Find a middle line opposite to the X-hub which partitions S into S L and S R , with equivalent sizes. Step 3: Recursively build curved frames for S L and S R , indicated as Hull(S L ) and Hull(S R ), separately.

Slide 19

Step 4: Apply the combining system to consolidate Hull(S L ) and Hull(S R ) together to shape an arched structure. Time unpredictability: T(n) = 2T(n/2) + O(n) = O(n log n)

Slide 20

The Voronoi Diagram Problem e.g. The Voronoi outline for three focuses Each L ij is the opposite bisector of the line.

Slide 21

Definition of Voronoi Diagrams Def : Given two focuses P i , P j  S, let H(P i ,P j ) indicate the half plane containing P i . The Voronoi polygon connected with P i is characterized as

Slide 22

Given an arrangement of n focuses, the Voronoi outline comprises of all the Voronoi polygons of these focuses. The vertices of the Voronoi outline are called Voronoi focuses and its sections are called Voronoi edges .

Slide 23

Delaunay Triangulation

Slide 24

Example for Constructing Voronoi Diagrams Divide the focuses into two sections.

Slide 25

Merging Two Voronoi Diagrams Merging along the piecewise direct hyperplane

Slide 26

The Final Voronoi Diagram After combining

Slide 27

Divide-and-Conquer for Voronoi Diagram Input: A set S of n planar focuses. Yield: The Voronoi graph of S. Step 1: If S contains stand out point, return. Step 2: Find a middle line L opposite to the X-pivot which separates S into S L and S R , with equivalent sizes.

Slide 28

Step 3: Construct Voronoi graphs of S L and S R recursively. Signify these Voronoi graphs by VD(S L ) and VD(S R ). Step 4: Construct a partitioning piece-wise straight hyperplane HP which is the locus of focuses all the while nearest to a point in S L and a point in S R . Toss all portions of VD(S L ) which mislead the privilege of HP and all fragments of VD(S R ) that deceive the left of HP. The subsequent chart is the Voronoi graph of S. (See points of interest on the following page.)

Slide 29

Merging Two Voronoi Diagrams into One Voronoi Diagram Input: (a) S L and S R where S L and S R are divided by an opposite line L. (b) VD(S L ) and VD(S R ). Yield: VD(S) where S = S L ∩S R Step 1: Find the raised frames of S L and S R , meant as Hull(S L ) and Hull(S R ), separately. (A unique calculation for discovering a raised body for this situation will by given later.)

Slide 30

Step 2: Find portions and which join HULL(S L ) and HULL(S R ) into a curved body (P an and P c fit in with S L and P b and P d have a place with S R ) Assume that lies above . Let x = a, y = b, SG= and HP =  . Step 3: Find the opposite bisector of SG. Mean it by BS. Let HP = HP∪{BS}. On the off chance that SG = , go to Step 5; generally, go to Step 4.

Slide 31

Step 4: The beam from VD(S L ) and VD(S R ) which BS first crosses with must be an opposite bisector of either or for some z. On the off chance that this beam is the opposite bisector of , then let SG = ; something else, let SG = . Go to Step 3. Step 5: Discard the edges of VD(S L ) which reach out to one side of HP and dispose of the edges of VD(S R ) which stretch out to one side of HP. The subsequent chart is the Voronoi outline of S = S L ∪S R .

Slide 32

Properties of Voronoi Diagrams Def : Given a point P and a set S of focuses, the separation in the middle of P and S is the separation in the middle of P and P i which is the closest neighbor of P in S. The HP acquired from the above calculation is the locus of focuses which keep equivalent separations to S L and S R . The HP is monotonic in y.

Slide 33

# of Voronoi Edges # of edges of a Voronoi graph  3n - 6, where n is # of focuses. Thinking: # of edges of a planar chart with n vertices  3n - 6. A Delaunay triangulation is a planar diagram. Edges in Delaunay triangulation edges in Voronoi outline.

Slide 34

# of Voronoi Vertices # of Voronoi vertices  2n - 4. Thinking : Let F, E and V signify # of face, edges and vertices in a planar chart. Euler ’ s connection: F = E - V + 2. In a Delaunay triangulation, V = n, E  3n – 6  F = E - V + 2  3n - 6 - n + 2 = 2n - 4.

Slide 35

Construct a Convex Hull from a Voronoi Diagram After a Voronoi outline is built, a curved structure can by found in O(n) time.

Slide 36

Construct a Convex Hull from a Voronoi Diagram Step 1 : Find an interminable beam by analyzing all Voronoi edges. Step 2 : Let P i be the point to one side of the interminable beam. P i is a raised structure vertex. Inspect the Voronoi polygon of P i to locate the following endless beam. Step 3 : Repeat Step 2 until we come back to the beginning beam.

Slide 37

Time Complexity Time many-sided quality for consolidating 2 Voronoi charts: Total: O(n) Step 1: O(n) Step 2: O(n) Step 3 ~ Step 5: O(n) (at most 3n - 6 edges in VD(S L ) and VD(S R ) and at most n portions in HP) Time intricacy for developing a Voronoi outline: O(n log n) b ecause T(n) = 2T(n/2) + O(n) = O(n log n)

Slide 38

The Lower Bound of the Voronoi Diagram Problem The lower bound of the Voronoi graph issue is  (n log n). sorting  Voronoi chart issue The Voronoi graph for an arrangement of focuses on a straight line

Slide 39

Applications of Voronoi Diagrams The Euclidean closest neighbor looking issue. The Euclidean all closest neighbor issue.

Slide 40

Fast Fourier Transform (FFT) Fourier change Inverse Fourier change Discrete Fourier transform(DFT) Given a 0 , a 1 , … , a n-1 , process

Slide 41

FFT Algorithm Inverse DFT : DFT can be re

Recommended
View more...