《算法设计(分治法-最近点对)》由会员分享，可在线阅读，更多相关《算法设计(分治法-最近点对)（26页珍藏版）》请在金锄头文库上搜索。
1、Date12007-2008-01Design and Analysis of AlgorithmsSCUECReview of last classbMultiplication of two lager integersbMultiplication of two square matrices Date22007-2008-01Design and Analysis of AlgorithmsSCUECDivide and Conquer (IV)Chapter 4l l Application to geometrical problem Application to geometri
2、cal problemn nThe closest pair problem The closest pair problemDate32007-2008-01Design and Analysis of AlgorithmsSCUECGoals of the LecturebAt the end of this lecture, you should Be familiar with the pigeonhole principle Understand the closest pair problem Master how to solve the closest pair problem
3、 based on divide and conquer techniqueDate42007-2008-01Design and Analysis of AlgorithmsSCUECThe Pigeonhole PrinciplebIf n balls are distributed into m boxes, then(1) one box must contain at least n/m balls, and(2) one box must contain at most n/m balls.Proof. (1) if all boxes less than n/m balls, t
4、hen the total number of balls at most m(n/m-1) m(n/m+(m-1)/m-1) = n+m-1-m nwhich is a contradiction.which is also a contradiction.Date52007-2008-01Design and Analysis of AlgorithmsSCUECThe closest-pair problemProblem description Let S be a set of n points in the plane, the problem is that how to fin
5、d a pair of points p and q in S whose mutual distance is smallest (see the following figure) In other words, we want to find two points p1(x1,y1),p2(x2,y2) in S with the propertythat the distance between themdefined byis the minimum among all pairsof points in SDate62007-2008-01Design and Analysis o
6、f AlgorithmsSCUEC1-Dimension Closest Pair1D closest pair can be solved in O(n log n) (how?). Above method, however, does not generalize to higher dimensions. So, lets develop a divide-and- conquer for 1D. Divide the points S into two sets S1,S2 by some x- coordinate so that p 3 Divede and Conquer 20
7、 A_POINT *SL = new A_POINT(high-low)/2+1; 21 A_POINT *SR = new A_POINT(high-low)/2;22 / divide X into two subarray by m 22 m = (high + low) / 2; 23 j = k = 0; 24 for (i=0; i 2, T(n) depends on the following parts: For loop (from row 24 to 28) copy the elements of Y into two auxiliary array according
8、 to their x-coordinate, need n copies. Two recursively call closest (row 29 and 30) to find the closest-pair of left subset of X and find the closest-pair of right subset of X, need 2T(n/2). For loop (from row 37 to 39) collect the points within the two strips of width d of L from Y, need n comparis
9、ons. Double for loop (from row 40 to 46) find the closest-pair with one point in each subset of X need 7n comparisons at worst. Date222007-2008-01Design and Analysis of AlgorithmsSCUECClosest Algorithm Analysis (cont.)bSpace complexity: So the time complexity recurrence relation can be write as foll
10、ows: The recurrence relation works out to:Date232007-2008-01Design and Analysis of AlgorithmsSCUECThinking and ExercisebSuppose we modify the algorithm for the closest pair problem so that not each point in Z is compared with seven points in Z. Instead, every point to the left of the vertical line L
11、 is compared with a number of points to its right.bHow many points to the right of L have to be compared with every point to its left? Why?bWhat are the necessary modifications to the algorithm?Date242007-2008-01Design and Analysis of AlgorithmsSCUECThe EndDate252007-2008-01Design and Analysis of AlgorithmsSCUECAssignmentsbReading assignment: Chapter 5bExercise: No 2 of exercises 4.6(p154)Date262007-2008-01Design and Analysis of AlgorithmsSCUEC
