Class Notes (809,509)
Canada (493,754)
CS 341 (26)

Lecture #5 - Closest pair and Linear Time Selection Fall 2009

12 Pages
Unlock Document

University of Waterloo
Computer Science
CS 341
Forbes Burkowski

Closest Pair and Linear Time Selection by Brancusi Closest Pair • Problem definition: –We are given n points p = (x, y), i = 1,…, n. i i i –How far apart are the closest pair of points? • We need the i and j values that minimize the Euclidean distance: 2 (xi− xj) +(yi− yj)2 • Then return this distance. –Brute force: compute distances for all n(n-1)/2 pairs and find the minimum. • This algorithm runs in time Θ(n 2). 1 Closest Pair by Divide and Conquer • Sort by x-coordinate, then : • Divide: – Find vertical line splitting points in half. • Conquer: – Recursively find closest pairs in each half. • Combine: – Check vertices near the border to see if any pair straddling the border is closer together than the minimum seen so far. • Our goal: – Θ(n) overhead so that the total run time is Θ(n log n). Implementation Details • Input: a set of points P sorted with respect to the x coordinate. • Initially, P = all points, and we pay Θ(n log n) to sort them before making the first call to the recursive subroutine. • Given the sorted points, it is easy to find the dividing line. – Let PLbe points to the left of the dividing line. – Let PRbe points to the right of the dividing line. 2 Closest Pair Implementation Details • Recursively: – Find closest pair in P : Let δ beLtheir separation distance – Similarly find closest pair in P , Rith separation distance δ R – Clever observation: If the closest pair straddles the dividing line, then each point of the pair must be within δ = min{δ ,Lδ }Rof the dividing line. • This will usually specify a fairly narrow band for our “straddling”search. Implementation Details – Suppose p and q, d(p,q)= δ δ are candidate closest points, with p on the left and q on the right of the dividing line. • q not to the right oδband. δ • if p = (x, y) then with y coords interval [y δ, y +δ] can be p successfully paired with p. – So, we need only look at points within δ above and below a horizontal line through p. δ – Since the points in this rectangle must be separated by at least δ we have at most 6 points to investigate.(Diagram shows thisDividingLinePossible point q “worst case” situation). 3 Closest Pair Pseudocode • Let P be a global array storing all the points with P Rnd P deLined as described earlier. • Let QL be the subset of points in P Lhat are at most δ (delta in the code) to the left of the dividing line. • Let QR be the subset of points in P Rhat are at most δ to the right of the dividing line. //-------- main --------- // P contains all the points sort P by x-coordinate; return closest_pair(1, n); Closest Pair Pseudocode function closest_pair(l,r) // Find the closest pair in P[l..r] (sorted by x-coordinate) if size(P) < 2 then return infinity; mid := (l + r)/2; midx := P[mid].x; dl := closest_pair(l, mid); dr := closest_pair(mid + 1, r); // Side effect: P[l..mid] and P[mid+1..r] are now sorted // wrt the y-coordinate delta := min(dl, dr); QL := select_candidates(l, mid, delta, midx); QR := select_candidates(mid + 1, r, delta, midx); dm := delta_m(QL, QR, delta); // Use merge to make P[l..r] sorted by y-coordinate Merge(l, mid, r); // Merge as in MergeSort return min(dm, dl, dr); 4 Closest Pair Pseudocode function select_candidates(l,r,delta,midx) // From P[l..r] select all points which are // at most delta from midx line create empty array Q; for i := l to r do if (abs(P[i].x - midx) <= delta) add P[i] to Q; return Q; Closest Pair Pseudocode function delta_m(QL,QR,delta) // Are there two points p in QL, q in QR such that // d(p,q)<=delta? Return distance of closest pair. // Assume QL and QR are sorted by the y coordinate. j := 1; dm := delta; for i := 1 to size(QL) do p := QL[i]; // find the bottom-most candidate from QR while (j <= size(QR) and QR[j].y < p.y-delta) do j := j+1; // check all candidates from QR starting with j k := j; while (k <= size(QR) and QR[k].y <= p.y + delta) do dm := min(dm, distance(p, QR[k])); k := k+1; return dm; 5 Closest Pair Analysis – Let T(n) be the time required to solve the problem for n points: • Divide: Θ(1) • Conquer: 2T (n/2) • Combine: Θ(n) – The precise form of the recurrence is: T(n) =T ( n/2 ) ( n/2 )+Θ(n) which we can approximate by: T(n) =2T n(2 + )(n) – Solution: Θ(n log n). Linear-Time Selection • Problem statement: – Given an array A of n numbers A[1..n] and a number i (1 < i < n), find i smallest number in A. th – Definition: Median of A is the n/2 element in A. • Example: If A = (7, 4, 8, 2, 4); then |A| = 5 and the 3 smallest element (and median) is 4. – Trivial solutions for our problem: th • Sort the array and find the i element. – Execution time: (n log n) • If i is small we can find i using a linear scan similar to finding a minimum or maximum in the array. Idea: keep current top i rather than current max only. 6 Linear-Time Selection (page 2) • Strategy: Partition-based (divide and conquer) selection – Choose one element p from array A (pivot element) – Split input into three s
More Less

Related notes for CS 341

Log In


Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.