Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |
| courses:cs211:winter2014:journals:colin:chapter5 [2014/03/12 05:48] – 5.2-4 mohnacsc | courses:cs211:winter2014:journals:colin:chapter5 [2014/03/12 05:56] (current) – [5.4 - Finding the Closest Pair of Points] mohnacsc |
|---|
| ==== 5.4 - Finding the Closest Pair of Points ==== | ==== 5.4 - Finding the Closest Pair of Points ==== |
| |
| | Given n points in the plane, find the pair that is closest together. This is done by dividing and comparing the closest points in each half. We sort the points by the x- and y-coordinates in two separate lists. The two lists are divided again into left and right sides of the plane. Determine a closest pair of points on each side. If there exists a pair of points, each in a separate set, with a smaller distance than that found in the respective subsets ($), then each of the point lies within $ of the dividing line. Following this logic, we need only search the points within $ of the dividing line for a better result than the separate sets of points. The running time of the algorithm is O(n log n). |
