CS341 Lecture Notes - Closest Pair Of Points Problem, Euclidean Distance, Subroutine

27 views12 pages
user avatar
Published on 16 Oct 2011
School
University of Waterloo
Department
Computer Science
Course
CS341
1
Closest Pair
and
Linear Time
Selection
The Kiss
by Brancusi
Closest Pair
Problem definition:
We are given npoints pi=(xi, yi), i = 1,, n.
How far apart are the closest pair of points?
We need the iand jvalues that minimize the
Euclidean distance:
Then return this distance.
Brute force: compute distances for all
n(n-1)/2pairs and find the minimum.
This algorithm runs in time Θ(n2).
xixj
( )2+(yiyj)2
Unlock document

This preview shows pages 1-3 of the document.
Unlock all 12 pages and 3 million more documents.

Already have an account? Log in
2
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 Psorted with respect to
the xcoordinate.
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.
Unlock document

This preview shows pages 1-3 of the document.
Unlock all 12 pages and 3 million more documents.

Already have an account? Log in
3
Closest Pair Implementation Details
• Recursively:
Find closest pair in PL: Let
δ
Lbe their separation
distance
Similarly find closest pair in PR, with separation
distance
δ
R.
Clever observation: If the closest pair straddles the
dividing line, then each point of the pair must be
within
δ
= min{
δ
L,
δ
R} of the dividing line.
This will usually specify a fairly narrow band for our
“straddlingsearch.
Implementation Details
Suppose pand q, d(p,q)=
δ
are candidate closest points,
with pon the left and qon the
right of the dividing line.
qnot to the right of
δ
band.
if p= (x, y)then with ycoords
interval [y-
δ
, y+
δ
] can be
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 this
“worst case” situation).
δ
δ
δ
p
Dividing Line Possible point q
Unlock document

This preview shows pages 1-3 of the document.
Unlock all 12 pages and 3 million more documents.

Already have an account? Log in

Document Summary

We are given n points pi = (xi, yi), i = 1, , n. How far apart are the closest pair of points: we need the i and j values that minimize the. Y j )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 q (n2). 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: Q (n) overhead so that the total run time is q (n log n). Let pl be points to the left of the dividing line. Let pr be points to the right of the dividing line. Find closest pair in pl: let d distance.