Class Notes
(809,509)

Canada
(493,754)

University of Waterloo
(18,194)

Computer Science
(752)

CS 341
(26)

Forbes Burkowski
(15)

Lecture

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

Unlock Document

University of Waterloo

Computer Science

CS 341

Forbes Burkowski

Fall

Description

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