CS341 Lecture Notes - Closest Pair Of Points Problem, Euclidean Distance, Subroutine
Document Summary
We are given n points pi = (xi, yi), i = 1, , n. How far apart are the closest pair of points: we need the i and j values that minimize the. Y j )2: then return this distance. Brute force: compute distances for all n(n-1)/2 pairs and find the minimum: this algorithm runs in time q (n2). Closest pair by divide and conquer: sort by x-coordinate, then, divide: Find vertical line splitting points in half: conquer: Recursively find closest pairs in each half: combine: Check vertices near the border to see if any pair straddling the border is closer together than the minimum seen so far: our goal: Q (n) overhead so that the total run time is q (n log n). Let pl be points to the left of the dividing line. Let pr be points to the right of the dividing line. Find closest pair in pl: let d distance.