Closest Pair Problem
Jump to navigation
Jump to search
Problem Description
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 airtraffic 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.
Bounds Chart
Step Chart
Improvement Table
Complexity Classes  Algorithm Paper Links  Lower Bounds Paper Links 

Exp/Factorial  
Polynomial > 3  
Cubic  
Quadratic  [ Naive Implementation (1975)]  
nlogn  Fortune and Hopcroft (1979)
F. Preparata and M. Shamos (1986) Bentley (1980) Bentley; Shamos (1976) Hinrichs; Nievergelt; Schorn (1988) Shamos; Hoey (1975) 

Linear  Rabin' Algorithm (1976)  
logn 