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 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.
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 |