# MIT 6 838 - Closest Pair (15 pages)

Previewing pages 1, 2, 3, 4, 5 of 15 page document
View Full Document

# Closest Pair

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

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
##### Algorithms for Computer Animation Documents
• 21 pages

• 56 pages

• 18 pages

• 2 pages

• 30 pages

• 80 pages

• 79 pages

• 13 pages

• 41 pages

• 16 pages

• 82 pages

• 19 pages

• 78 pages

• 41 pages

• 17 pages

• 16 pages

• 20 pages

• 25 pages

• 41 pages

• 25 pages

• 79 pages

• 80 pages

• 17 pages

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

Unlocking...