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

Section 4 The Divide-and-Conquer Strategy

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

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

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.

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

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 )

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

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 .

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)

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

At most 6 focuses in territory A:

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 ).

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)

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.

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

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.)

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

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.

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)

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

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

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 .

Delaunay Triangulation

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

Merging Two Voronoi Diagrams Merging along the piecewise direct hyperplane

The Final Voronoi Diagram After combining

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.

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.)

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.)

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.

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 .

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.

# 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.

# 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.

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

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.

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)

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

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

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

FFT Algorithm Inverse DFT : DFT can be re