CS341 Lecture Notes - Closest Pair Of Points Problem, Euclidean Distance, Subroutine
27 views12 pages
• 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
• Then return this distance.
–Brute force: compute distances for all
n(n-1)/2pairs and find the minimum.
• This algorithm runs in time Θ(n2).
Closest Pair by Divide and Conquer
• Sort by x-coordinate, then:
– Find vertical line splitting points in half.
– Recursively find closest pairs in each half.
– 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).
• Input: a set of points Psorted with respect to
• Initially, P= all points, and we pay Θ(n log n)
to sort them before making the first call to the
• Given the sorted points, it is easy to find the
– Let PLbe points to the left of the dividing line.
– Let PRbe points to the right of the dividing line.
Closest Pair Implementation Details
– Find closest pair in PL: Let
Lbe their separation
– Similarly find closest pair in PR, with separation
– Clever observation: If the closest pair straddles the
dividing line, then each point of the pair must be
R} of the dividing line.
• This will usually specify a fairly narrow band for our
– 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
• if p= (x, y)then with ycoords
] can be
successfully paired with p.
– So, we need only look at points
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).
Dividing Line Possible point q
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.