Transcription of Closest Pair Problem
{{id}} {{{paragraph}}}
Example: air traffic controller
Closest Pair Problem
Subhash SuriUC Santa BarbaraClosest Pair Problem Givennpoints ind-dimensions, find twowhose mutual distance is smallest. Fundamental Problem in manyapplications as well as a key step in A naive algorithm takesO(dn2)time. Element uniqueness reduces to ClosestPair, so (nlogn)lower bound. We will develop a divide-and-conquerbasedO(nlogn)algorithm ; dimensiondassumed SuriUC Santa Barbara1-Dimension Problem 1D Problem can be solved inO(nlogn)viasorting. Sorting, however, does not generalize tohigher dimensions. So, let s develop adivide-and-conquer for 1D.
Subhash Suri UC Santa Barbara 1-Dimension Problem † 1D problem can be solved in O(nlogn) via sorting. † Sorting, however, does not generalize to higher dimensions. So, let’s develop a divide-and-conquer for 1D. † Divide the points S into two sets S1;S2 by some x-coordinate so that p < q for all p 2 S1 and q 2 S2. † Recursively compute closest pair (p1;p2) in S1 and (q1;q2) in …
Loading..
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: