Randomized Incremental Construction in Algorithms CS648
Dive into the concepts of randomized incremental construction in CS648 algorithms through backward analysis and forward analysis. Explore the Find-Min problem, algorithms, probabilities, and more in this detailed lecture content.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Randomized Algorithms CS648 Lecture 16 Randomized Incremental Construction (Backward analysis) 1
PROBLEM 1 FIND-MIN PROBLEM 2
Find-Min algorithm A ? ? 1 2 ?: no. of times ??? is updated. Find-Min(A[1..?]) { ??? A[1]; For? = ? to ?do { if (A[?] < ???) ??? A[?] ; } return ???; } ??= ? if??? is updated in ?th iteration ? otherwise ? = ? + ?>??? = ? + ?>??(??= ?) ? ? = ? + ?>??[??] Probability that ?? A[?] is smaller than {A[?], , A[? ?]} 3
Forward analysis for ?(??= ?) First ? ?elements A ? ? ? 1 2 Notations: ?? ?: set of all subsets of A of size ? ?. For any ? ?? ?, ??: first ? ?elements of A are some permutation of ?. Find-Min(A[1..?]) { ??? A[1]; For? = ? to ?do { if (A[?] < ???) ??? A[?] ; } return ???; } Using Partition Theorem, ?(??= ?) = ? ?? ? ?(??= ? ?? ?(??) 4
Forward analysis for ?(??= ?) ? : a subset of ? ? elements. ?(??= ? ?? = Given that first ? ? elements of A are some permutation of ?, what is prob. that ??= ?? For this event to happen, A[?] must be smaller than every element of ?. ?(??= ? ?? depends upon ?. For example, if the smallest element of ? has rank ? in A, then ?(??= ? ??= ?? = ?? ? ? + ? ? ? Dependency on ? makes it hard to calculate ? ?? ? ?(??= ? ?? ?(??) 5
Backward analysis for ?(??= ?) First ?elements A ? ? ? 1 2 Notations: ??: set of all subsets of A of size ?. For any ? ??, ??: first ?elements of A are some permutation of ?. Find-Min(A[1..?]) { ??? A[1]; For? = ? to ?do { if (A[?] < ???) ??? A[?] ; } return ???; } Using Partition Theorem, ?(??= ?) = ? ?? ?(??= ? ?? ?(??) 6
Backward analysis for ?(??= ?) ? : a subset of ? ? elements. ?(??= ? ?? = Given that first ? elements of A are some permutation of ?, what is prob. that ??= ?? For this event to happen, the smallest element of ? must appear at A[?]. ?(??= ? ?? = ?( the smallest element of ? appear at A[?] ?? ) Fact: A is permuted randomly uniformly Every element of ? is equally likely to appear at place A[?]. ? ? ?(??= ? ?? = ?? Same for each ? 7
Backward analysis for ?(??= ?) First ?elements A ? ? ? 1 2 Notations: ??: set of all subsets of A of size ?. For any ? ??, ??: first ?elements of A are some permutation of ?. Find-Min(A[1..?]) { ??? A[1]; For? = ? to ?do { if (A[?] < ???) ??? A[?] ; } return ???; } Using Partition Theorem, ?(??= ?) = ? ?? ?(??= ? ?? ?(??) =? ? ? ?? ?(??) =? ? ? ? ? 8
PROBLEM 2 CLOSEST PAIR OF POINTS 9
Closest Pair of Points Problem Definition: Given a set ? of ? > ? points in plane, compute the pair of points with minimum Euclidean distance. Randomized algorithm: O(?) : Randomized Incremental Construction based algorithm 10
?th iteration Grid structure for first ? ? points ?? ? ?? ? 11
Analysis of ?th iteration Closest-pair-algorithm(?) Let <??,??, ,?? > be a uniformly random permutation of ?; ?? distance(??,??); ? Build_Grid(??,{??,??}); For? = ? to ? do { Step 1: locate the cell of the grid ? containing ??; Step 2: find the point ? {??, ,?? ?} closest to ??; let ? = distance(?, ??); Step 3: If? > ?? ? ?? ?? ?; Insert(??,?); Else ?? ?; ? Build_Grid(?,{??, ,??}); } return ??; O(1) O(1) O(1) ?? for constant ? 12
running time of ?th iteration ??: running time of ?th iteration O(1) + ?? ?(??< ?? ?) E[??] = ?? Question: What is ?(??< ?? ?) ? 13
Forward analysis for ?(??< ?? ?) Closest-pair-algorithm(?) Let <??,??, ,?? > be a uniformly random permutation of ?; ?? distance(??,??); ? Build_Grid(??,{??,??}); For? = ? to ? do { Step 1: locate the cell of the grid ? containing ??; Step 2: find the point ? {??, ,?? ?} closest to ??; let ? = distance(?, ??); Step 3: If? > ?? ? ?? ?? ?; Insert(??,?); Else ?? ?; ? Build_Grid(?,{??, ,??}); } return ??; 14
Forward analysis for ?(??< ?? ?) ? : a subset of ? ? points from ?. ??: first? ? points of ? are some permutationof? ?? ? Depends upon ? ?(??< ?? ? ?? = ?? ?? ? Calculating?(??< ?? ?) : Let ?? ? be the set of all subsets of ? of size ? ?. ?(??< ?? ?)= ? ???(??< ?? ? ?? ?(??) Grid structure for first ? ? points 15
Backward analysis for ?(??< ?? ?) Closest-pair-algorithm(?) Let <??,??, ,?? > be a uniformly random permutation of ?; ?? distance(??,??); ? Build_Grid(??,{??,??}); For? = ? to ? do { Step 1: locate the cell of the grid ? containing ??; Step 2: find the point ? {??, ,?? ?} closest to ??; let ? = distance(?, ??); Step 3: If? > ?? ? ?? ?? ?; Insert(??,?); Else ?? ?; ? Build_Grid(?,{??, ,??}); } return ??; 16
Backward analysis for ?(??< ?? ?) ? : a subset of ? points from ?. ??: first ? points of ?are some permutation of ? ? ? ?(??< ?? ? ?? = ?? ?? Calculating?(??< ?? ?) : Let ?? be the set of all subsets of ? of size ?. ?(??< ?? ?)= ? ???(??< ?? ? ?? ?(??) ?? ? ? ?(??) = ? ?? = ? ? ? ???(??) = ? ? Grid structure for first ? points 17
running time of ?th iteration ??: running time of ?th iteration E[??] = O(1) + ?? ?(??< ?? ?) = O(1) + ?? ? ? = O(1) Expected running time of the algorithm : = O(?) = O(1) E[??] ? ? ? ? Theorem: There exists a linear time Las Vegas algorithm to compute closest pair of points in plane. 18
RANDOMIZED INCREMENTAL CONSTRUCTION 19
Randomized Incremental Construction Permute the elements of input randomly uniformly. Build the structure incrementally. Keep some data structure to perform ?th iteration efficiently. Use Backward analysis to analyze the expected running time. 20
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. 21
PROBLEM 3 CONVEX HULL OF POINTS 22
Convex hull of Points Problem definition: Given ?points in a plane, compute a convex polygon of smallest area that encloses all the points. 23
Convex hull of Points Deterministic algorithm: O(? ??? ?) time algorithm. Many algorithms exist: Grahams Scan, Jarvis s march, divide and conquer, Randomized algorithm: O(? ??? ?) time algorithm. Based on Randomized Incremental Construction. Generalizable to higher dimensions. 24
Randomized algorithm for convex hull Convex-hull-algorithm(?) { Let <??,??, ,?? > be a uniformly random permutation of ?; ? triangle(??,??,??); For? = ? to ? do insert ?? and update ? return ?; } 25
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 ? = ?? + ? 26
Conflict graph : a powerful data structure ? ? points cones ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? 27
Before entering the for loop ? ? points cones ?? ?? ?? ?? ?? ?? 29
?th iteration ?? ?? ?? ?? ?? ?? ?? ?? 31
?th iteration ? ? points cones ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? 32
?th iteration ? ? points cones ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? 33
?th iteration ? ? points cones ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? 34
?th iteration ? ? points cones ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? 35
?th iteration ? ? points cones ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? 36
?th iteration ? ? points cones ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? 37
?th iteration ? ? points cones ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? 38
?th iteration ? ? points cones ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? 39
?th iteration ? ? points cones ?? ?? ?? ? ? ?" ?? ?? ?" ?? ?? ?? 40
Running time of ?th iteration Running time of ?th iteration is of the order of Number of edges destroyed Total time for ? iterations = O(?) Number of new edges created Number of points in the two adjacent cones that get created ?? Question: What is the max. number of new edges created in an iteration ? Answer: 2 Number of edges created during the algorithm = O(?) Since every edge destroyed was once created, so Total number of edges destroyed <Total number of edges decreated 41
Backward analysis of ?th iteration ? : a subset of ? points from ?. ??: first ? points of ?are some permutation of ? ?[?? ?? = ?? 42
Backward analysis of ?th iteration ? : a subset of ? points from ?. ??: first ? points of ?are some permutation of ? ?? ?? ?? ?? ?? ?? ?? ?[?? ?? = ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? 43
Backward analysis of ?th iteration ? : a subset of ? points from ?. ??: first ? points of ?are some permutation of ? ?? ?? ?? ?? ?? ?? ?? ?[?? ?? = ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? 44
Backward analysis of ?th iteration ? : a subset of ? points from ?. ??: first ? points of ?are some permutation of ? ?? ?? ?? ?? ?? ?? ?(? ?) ? ?? ?[?? ?? = ?? ?? ?? Calculating?[??] : ?? ?? Let ?? be the set of all subsets of ? of size ?. ?? ?? = ? ???[?? ?? ?(??) ?(? ?) ? =?(? ?) ? ?[??] = ?? ?? = ? ?? ?(??) ?? 45
Running time of the algorithm Expected running time of ith iteration = ?[??] + O(1) = O(? ? ?) Expected running time of the algorithm = O(? ??? ? ) Theorem: There is an O(? ??? ? ) time Las Vegas algorithm for computing convex hull. 46
