# MIT 6 838 - Closest Pair (15 pages)

Previewing pages*1, 2, 3, 4, 5*of 15 page document

**View the full content.**# Closest Pair

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

**View the full content.**View Full Document

## Closest Pair

0 0 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