Skip to content
Algorithm Atlas
GeometryAll categories
ExtendedSource checked

Closest Pair of Points

Finds the two points with the smallest distance between them.

Explore relationshipsOpen constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category
Geometry
Difficulty
Intermediate
Family
Divide and Conquer Geometry
Tier
Extended
Status
Verified
Review
Source Checked
Sources
2
Formulas
1
Relationships
1
Code example
Ready
Visualization
Ready

Overview

The classic closest-pair algorithm sorts points, divides the plane, and checks only a narrow strip around the split after solving both halves.

Core Concepts

divide and conquerdistance metricsplit stripsorted points

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n log n)

Average

O(n log n)

Worst

O(n log n)

Space

O(n)

When to Use

  • Use when the exact closest pair is needed for many points.
  • Use when spatial analysis is a central requirement.

When Not to Use

  • Avoid when approximate nearest-neighbor search is enough and much faster to update dynamically.
  • Avoid when floating-point precision or degenerate geometry cannot be handled robustly.

What It Does

  • Sorts points by coordinate
  • Solves closest pairs recursively
  • Checks a narrow split strip

Use Cases

  • Spatial analysis
  • Collision proximity checks
  • Clustering preprocessing

Inputs

  • Set of 2D points

Outputs

  • Closest point pair
  • Distance between them

Key Formulas (1)

Euclidean distance

distance(a, b) = √(a.x − b.x)2 + (a.y − b.y)2
distance(a, b) = sqrt((a.x - b.x)^2 + (a.y - b.y)^2)

Measures the separation minimized by the algorithm.

Pseudocode

  1. 1.Sort points by x coordinate
  2. 2.Recursively solve left and right halves
  3. 3.Keep the smaller distance
  4. 4.Build a strip near the split line
  5. 5.Check limited neighboring points in strip order

Canonical Example

Input
points = [(0,0), (5,5), (1,1)]
Output
closest = [(0,0), (1,1)]
Explanation
The pair with smallest Euclidean distance is returned.

Implementation Notes

  • Carry y-sorted lists through recursion for the standard O(n log n) version.
  • Use robust predicates or tolerances when near-degenerate inputs are expected.
  • Keep a tiny example with expected output beside the implementation.

Common Pitfalls

  • Checking too many strip pairs accidentally falls back toward quadratic time.
  • Collinear, overlapping, and duplicate points need explicit tie-breaking rules.
  • Not defining boundary, empty, or degenerate inputs before implementation.

Interactive Mechanism Walkthrough

Spatial Primitive & Sweep-Line Canvas

Show the split line and narrow strip where cross-boundary closest pairs can appear.

Closest Pair of Points mechanism walkthrough step 1 of 5
Step 1 of 5: Sort points by x coordinate
geometry-diagram

Notes

Keeping points sorted by y coordinate avoids extra sorting in each recursive call.

Sources (2)

What each reference supports for this entry.

Computational Geometry: Algorithms and Applications

Book

Computational geometry textbook support for Closest Pair of Points's geometric model, data structures, and robustness concerns.

Open source

The Algorithm Design Manual

Book

Algorithm catalog support for Closest Pair of Points's problem context, known alternatives, and practical selection tradeoffs.

Open source

Explore Next

Good next jumps from the relationship graph, ranked for useful discovery.

Open discoveryOpen map
Alternative tok-d Tree

Data Structures · Core

Closest-pair algorithms and k-d trees are different approaches to nearest-neighbor-style geometry queries.

Compare with this

Relationships

View full relationship page
Alternative tok-d Tree

Closest-pair algorithms and k-d trees are different approaches to nearest-neighbor-style geometry queries.

Related Algorithms

Convex Hullk-d Tree

Tags

GeometryComputational GeometryDivide and Conquer