Closest Pair Problem
Revision as of 10:54, 10 October 2022 by Admin (talk | contribs) (Created page with "== 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 == File:Closest_Pair_ProblemBoundsChart.png|1050...")
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 |