MIT 6 838 - Closest Pair (15 pages)

Previewing pages 1, 2, 3, 4, 5 of 15 page document View the full content.
View Full Document

Closest Pair



Previewing pages 1, 2, 3, 4, 5 of actual document.

View the full content.
View Full Document
View Full Document

Closest Pair

44 views

Lecture Notes


Pages:
15
School:
Massachusetts Institute of Technology
Course:
6 838 - Algorithms for Computer Animation

Unformatted text preview:

Closest Pair Piotr Indyk March 29 2005 Lecture 12 Closest Pair 1 Closest Pair Find a closest pair among p1 pn Rd Easy to do in O dn2 time For all pi pj compute pi pj and choose the minimum We will aim for better time as long as d is small For now focus on d 2 March 29 2005 Lecture 12 Closest Pair 2 Divide and conquer Divide Compute the median of xcoordinates Split the points into PL and PR each of size n 2 Conquer compute the closest pairs for PL and PR Combine the results the hard part March 29 2005 Lecture 12 Closest Pair 3 Combine 2k Let k min k1 k2 Observe k2 Need to check only pairs which cross the dividing line Only interested in pairs within distance k k1 Suffices to look at points in the 2k width strip around the median line March 29 2005 Lecture 12 Closest Pair 4 Scanning the strip Sort all points in the strip by their ycoordinates forming q1 qt t n Let yi be the y coordinate of qi kmin k For i 1 to t k k k k k j i 1 While yi yj k If qi qj kmin then kmin qi qj j j 1 Report kmin and the corresponding pair March 29 2005 Lecture 12 Closest Pair 5 Analysis Correctness easy Running time is more involved Can we have many qj s that are within distance k from qi No Proof by packing argument March 29 2005 Lecture 12 Closest Pair k 6 Analysis ctd Theorem there are at most 7 qj s j i such that yi yj k Proof Each such qj must lie either in the left or in the right k k square Within each square all points have distance distance k from others We can pack at most 4 such points into one square so we have 8 points total incl qi March 29 2005 Lecture 12 Closest Pair qi 7 At most 4 Split the square into 4 subsquares of size k 2 k 2 Diameter of each square is k 21 2 k at most one point per sub square March 29 2005 Lecture 12 Closest Pair 8 Running time Divide O n Combine O n log n because we sort by y However we can Sort all points by y at the beginning Divide preserves the y order of points Then combine takes only O n We get T n 2T n 2 O n so T n O n log n March 29 2005



View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Closest Pair and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Closest Pair and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?