All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Description

Randomized Algorithms CS648 Lecture 18 Randomized Incremental Construction (part II) 1 RANDOMIZED INCREMENTAL CONSTRUCTION 2 Randomized Incremental Construction Permute the elements of input randomly uniformly.

Transcript

Randomized Algorithms CS648 Lecture 18 Randomized Incremental Construction (part II) 1 RANDOMIZED INCREMENTAL CONSTRUCTION 2 Randomized Incremental Construction Permute the elements of input randomly uniformly. Build the structure incrementally. Keep some data structure to perform ith iteration efficiently. Use Backward analysis to analyze the expected running time. 3 Randomized Incremental Construction Convex Hull of a set of points Trapezoidal decomposition of a set of segments. Convex polytope of a set of half-planes Smallest sphere enclosing a set of points. Linear programming in finite dimensions. 4 Trapezoidal decomposition O((n + m) log n ) time O(m + n log n ) time 5 PROBLEM 3 CONVEX HULL OF POINTS 6 Convex hull of Points Problem definition: Given n points in a plane, compute a convex polygon of smallest area that encloses all the points. 7 Convex hull of Points Deterministic algorithm: O(n log n) time algorithm. Many algorithms exist: Grahams Scan, Jarvis s march, divide and conquer, Randomized algorithm: O(n log n) time algorithm. Based on Randomized Incremental Construction. Generalizable to higher dimensions. 8 Randomized algorithm for convex hull Convex-hull-algorithm(P) { Let p 1,p 2,,p n be a uniformly random permutation of P; H triangle(p 1,p 2, p 3 ); For i = 4 to n do insert p i and update H return H; } 9 A simple exercise from geometry Exercise: Given a line L and two points p and q, determine whether the points lie on the same/different sides of L. L p q q y = mx + c 10 Conflict graph : a powerful data structure c 2 n i points cones c 7 c 8 c 3 c 4 c 2 c 3 c 4 c 5 c 6 c 7 c 5 c 8 c 6 11 12 Before entering the for loop n 3 points cones c 2 c 2 c 3 c 3 13 INSERTING ith POINT 14 ith iteration c 2 c 8 c 3 c 7 c 4 c 5 c 6 15 ith iteration c 2 n i + 1 points cones c 7 c 8 c 3 c 4 c 2 c 3 c 4 c 5 c 6 c 7 c 5 c 8 c 6 16 ith iteration c 2 n i + 1 points cones c 7 c 8 c 3 c 4 c 2 c 3 c 4 c 5 c 6 c 7 c 5 c 8 c 6 17 ith iteration c 2 n i + 1 points cones c 7 c 8 c 3 c 4 c 2 c 3 c 4 c 5 c 6 c 7 c 5 c 8 c 6 18 ith iteration c 2 n i points cones c 7 c 8 c 3 c 4 c 2 c 3 c 4 c 5 c 6 c 7 c 5 c 8 c 6 19 ith iteration c 2 n i points cones c 7 c 8 c 3 c 4 c 2 c 3 c 4 c 5 c 6 c 7 c 5 c 8 c 6 20 ith iteration c 2 n i points cones c 7 c 8 c 3 c 4 c 2 c 3 c 4 c 5 c 6 c 7 c 5 c 8 c 6 21 ith iteration c 2 n i points cones c 7 c 8 c 3 c 4 c 2 c 3 c 4 c 5 c 6 c 7 c 5 c 8 c 6 22 ith iteration c 2 n i points cones c 7 c 8 c 3 c 4 c c 2 c 3 c 4 c 5 c 6 c 7 c 5 c 8 c 6 23 ith iteration n i points cones c 8 c c c c 7 c c 6 c 7 c 8 c 6 24 Running time of ith iteration Running time of ith iteration is of the order of Number of edges of convex hull that are destroyed Number of new edges of convex hull that are created Total time for n iterations = O(n) Number of points in the two adjacent cones that get created X i Question: What is the max. number of new edges created in an iteration? Answer: 2 Number of edges created during the algorithm = O(n) Since every edge destroyed was once created, so Total number of edges destroyed Total number of edges created 25 Backward analysis of ith iteration a : a subset of i points from P. E a : first i points of P are some permutation of a Convex hull at the end of ith iteration E,X i E a =?? 26 Backward analysis of ith iteration c 8 p 8 p 1 p 2 c 2 c 3 a : a subset of i points from P. E a : first i points of P are some permutation of a E,X i E a =?? p 7 p 3 c 7 c 4 p 6 p 4 p 5 c 5 c 6 27 Backward analysis of ith iteration c 8 p 8 p 1 p 2 c 2 c 3 a : a subset of i points from P. E a : first i points of P are some permutation of a E,X i E a =?? p 7 p 3 n 1 + n 2 c 7 c 4 n 2 + n 3 p 6 p 4 n 3 + n 4 n 4 + n 5 p 5 c 5 c 6 28 Backward analysis of ith iteration c 8 p 8 p 1 c 2 p 2 c 3 a : a subset of i points from P. E a : first i points of P are some permutation of a E,X i E a =?? c 7 p 7 p 6 p 5 p 3 p 4 c 5 c 4 n 1 + n 2 + n 2 + n 3 + n 3 + n 4 + n 4 + n i 1 i 1 i 1 i c 6 n 7 + n 8 + n 8 + n 1 1 i 1 i 29 Backward analysis of ith iteration a : a subset of i points from P. c 8 p 8 p 1 p 2 c 2 c 3 E a : first i points of P are some permutation of a E,X i E a =?? 2(n i) i p 7 p 3 Calculating E,X i - : c 7 c 4 Let S i be the set of all subsets of p 6 p 4 P of size i. c 6 p 5 c 5 E,X i - = = a S i a S i E,X i E a P(E a ) 2(n i) i P(E a ) = 2(n i) i 30 Running time of the algorithm Expected running time of ith iteration = E,X i - + O(1) = O( n i i ) Expected running time of the algorithm = O(n log n ) Theorem: There is an O(n log n ) time Las Vegas algorithm for computing convex hull. 31 USING BACKWARD ANALYSIS FOR MISCELLANEOUS APPLICATIONS 32 PROBLEM 1 SMALLEST ENCLOSING CIRCLE 33 Smallest Enclosing Circle 34 Smallest Enclosing Circle Question: Suppose we sample k points randomly uniformly from a set of n points, what is the expected no. of points that remain outside the smallest circle enclosing the sample? For k= n, the answer is PROBLEM 2 SMALLEST LENGTH INTERVAL 36 Sampling points from a unit interval Question: Suppose we select k points randomly uniformly from interval [0,1], what is expected length of the smallest sub-interval? for k = 1, it is?? for k = 2, it is?? 1 General solution :?? k This bound can be derived using two methods. relationship between uniform distribution and exponential distribution. Backward analysis. PROBLEM 3 MINIMUM SPANNING TREE 38 Minimum spanning tree b 22 h 1 6 a v 12 u 3 15 c d y x 39 Minimum spanning tree b 22 h 1 6 a v 12 u 3 15 c d y x 40 Light Edge b 22 h 6 1 a v 3 12 u Definition: Let a E. An edge e E\a is said to be light with respect to a if c d MST(*e+ a) MST(a) 16 9 y 18 5 x Question: If a r E and a = k, how many edges from E\a are light with respect to a on expectation? Answer:?? n (m k) k 41 Smallest Enclosing Circle Let C be smallest enclosing circle for set P of point. Facts from high school geometry C is defined by 2 or 3 points lying on its boundary. 42 Smallest Enclosing Circle Let C be smallest enclosing circle for set P of point. Facts from high school geometry C is defined by 2 or 3 points lying on its boundary. Not the smallest enclosing circle Since the defining points form an obtuse triangle. 43 Smallest Enclosing Circle Let C be smallest enclosing circle for set P of point. Facts from high school geometry C is defined by 2 or 3 points lying on its boundary. This is the smallest enclosing Circle since the defining points form an acute angle triangle. 44 Smallest Enclosing Circle Let C be smallest enclosing circle for set P of point. Facts from high school geometry C is defined by 2 or 3 points lying on its boundary. Lemma 1: If p lies outside C, p must be one of the defining point of smallest enclosing circle of P *p+ 45 Smallest Enclosing Circle Randomized Incremental Construction Smallest-Enclosing-Circle(P) { Let p 1,p 2,,p n be a uniformly random permutation of P; C Circle(p 1,p 2 ); For i = 3 to n do return H; }? if ( p i lies outside C ) update C; Question: How many times will C be updated? X i = 1 if C is udated in ith iteration 0 otherwise 46 Question: What is P[X i = 1]? Smallest Enclosing Circle Smallest Enclosing Circle at the end of ith iteration 47 Question: What is P[X i = 1]? Smallest Enclosing Circle 3 Using Lemma 1 i Use it to solve the given problem. 48 PROBLEM 3 MINIMUM SPANNING TREE 49 Minimum spanning tree b 22 h 1 6 a v 12 u 3 15 c d y x 50 Minimum spanning tree 17 d 16 9 b 22 h 1 6 a v 12 u c y 18 5 x Algorithms: Prim s algorithm Kruskal s algorithm Boruvka s algorithm Less known but it is the first algorithm for MST 51 Minimum spanning tree G = (V, E) : undirected graph with weights on edges n = V, m = E. Deterministic algorithms: Prim s algorithm 1. O((m + n) log n) using Binary heap 2. O(m + n log n) using Fibonacci heap Best deterministic algorithm: O(m + n log n) bound Too complicated to design and analyze Fails to beat Prim s algorithm using Binary heap 52 Minimum spanning tree G = (V, E) : undirected graph with weights on edges n = V, m = E. Randomized algorithm: Karger-Klein-Tarjan s algorithm [1995] 1. Las Vegas algorithm 2. O(m + n) expected time This algorithm uses Random sampling MST verification algorithm Boruvka s algorithm Elementary data structure We will discuss this milestone result in the next class. 53

Related Search

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks