Closest Pair Problem
We are given an array of n points in the plane, and the problem is to find out the closest pair of points in the array. This problem arises in a number of applications. For example, in air-traffic control, you may want to monitor planes that come too close together, since this may indicate a possible collision. Recall the following formula for distance between two points p and q.
|Complexity Classes||Algorithm Paper Links||Lower Bounds Paper Links|
|Polynomial > 3|
|Quadratic||[- Naive Implementation (1975)]|
|nlogn||Fortune and Hopcroft (1979)|
|Linear||Rabin' Algorithm (1976)|