Closest Pair of Points

Divide & Conquer — median split, the 2δ strip, and the bounded comparisons

Brute force O(n²) Divide & Conquer O(n log n) Sweep line O(n log n) Randomized grid O(n) exp

Speed:Slow Fast

Step: 0/0

delta: ∞

Comparisons: 0

Recursion depth: 0

Points: 0

point median line strip (|x−mid|<δ) comparing closest pair active region

What's happening

Press Start to run the divide-and-conquer closest-pair algorithm, or Step to advance one step at a time.

Complexity

Approach	Time	Space
Brute force	O(n²)	O(1)
Divide & conquer	O(n log n)	O(n)
Sweep line	O(n log n)	O(n)
Randomized grid	O(n) exp	O(n)
Strip scan / point	O(1) (≤7)	—
Lower bound	Ω(n log n)	—

Operation Log