Closest Pair Problem

From Algorithm Wiki
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

Closest Pair ProblemBoundsChart.png

Step Chart

Closest Pair ProblemStepChart.png

Improvement Table

Complexity Classes Algorithm Paper Links Lower Bounds Paper Links
Polynomial > 3
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)

Khuller; Matias Randomized Sieve (1995) Dyer (1980)