Closest Pair of Points
Find two closest points in 2D plane. Divide-and-conquer approach achieves O(n log n). Classic algorithm demonstrating geometric divide-and-conquer.
Visualization
Interactive visualization for Closest Pair of Points
Closest Pair of Points
• Time: O(n²) brute force
• O(n log n) with divide & conquer
• Classic computational geometry problem
Interactive visualization with step-by-step execution
Implementation
1function closestPair(points: Point[]): [Point, Point, number] {
2 const n = points.length;
3 const sortedX = [...points].sort((a, b) => a.x - b.x);
4 const sortedY = [...points].sort((a, b) => a.y - b.y);
5
6 return closestPairRec(sortedX, sortedY);
7}
8
9function closestPairRec(px: Point[], py: Point[]): [Point, Point, number] {
10 const n = px.length;
11
12 if (n <= 3) {
13 return bruteForce(px);
14 }
15
16 const mid = Math.floor(n / 2);
17 const midPoint = px[mid];
18
19 const pyl: Point[] = [];
20 const pyr: Point[] = [];
21 for (const p of py) {
22 if (p.x <= midPoint.x) pyl.push(p);
23 else pyr.push(p);
24 }
25
26 const [p1L, p2L, dL] = closestPairRec(px.slice(0, mid), pyl);
27 const [p1R, p2R, dR] = closestPairRec(px.slice(mid), pyr);
28
29 let d = Math.min(dL, dR);
30 let pair: [Point, Point] = dL < dR ? [p1L, p2L] : [p1R, p2R];
31
32 const strip: Point[] = [];
33 for (const p of py) {
34 if (Math.abs(p.x - midPoint.x) < d) {
35 strip.push(p);
36 }
37 }
38
39 for (let i = 0; i < strip.length; i++) {
40 for (let j = i + 1; j < strip.length && strip[j].y - strip[i].y < d; j++) {
41 const dist = distance(strip[i], strip[j]);
42 if (dist < d) {
43 d = dist;
44 pair = [strip[i], strip[j]];
45 }
46 }
47 }
48
49 return [pair[0], pair[1], d];
50}
51
52function bruteForce(points: Point[]): [Point, Point, number] {
53 let minDist = Infinity;
54 let pair: [Point, Point] = [points[0], points[1]];
55
56 for (let i = 0; i < points.length; i++) {
57 for (let j = i + 1; j < points.length; j++) {
58 const d = distance(points[i], points[j]);
59 if (d < minDist) {
60 minDist = d;
61 pair = [points[i], points[j]];
62 }
63 }
64 }
65
66 return [pair[0], pair[1], minDist];
67}
68
69function distance(p1: Point, p2: Point): number {
70 return Math.sqrt((p1.x - p2.x) ** 2 + (p1.y - p2.y) ** 2);
71}Deep Dive
Theoretical Foundation
Divide points by vertical line into two halves, recursively find closest pair in each. Check pairs crossing the dividing line within distance δ (minimum of two halves). Key insight: only need to check 7 points in strip for each point.
Complexity
Time
O(n log n)
O(n log n)
O(n log n)
Space
O(n)
Applications
Industry Use
Nearest neighbor search in databases
Clustering algorithms in machine learning
Geographic analysis (closest facilities)
Computer graphics (collision detection)
Astronomy (stellar pair analysis)
Molecular dynamics simulations
Network analysis (closest node pairs)
Image processing (feature matching)
Use Cases
Related Algorithms
Merge Sort (Divide & Conquer Paradigm)
Classic divide-and-conquer sorting algorithm that recursively divides array into halves until single elements, then merges sorted subarrays. Invented by John von Neumann in 1945, it's one of the most efficient general-purpose sorting algorithms with guaranteed O(n log n) performance. The algorithm perfectly demonstrates the divide-and-conquer paradigm: divide problem, solve subproblems recursively, combine solutions.
Binary Search (Divide & Conquer)
Efficient search algorithm for sorted arrays using divide-and-conquer. At each step, eliminate half of remaining elements by comparing target with middle element. One of the most fundamental algorithms in computer science with O(log n) time complexity.
Closest Pair of Points
Find two points with minimum Euclidean distance among n points in 2D plane using divide-and-conquer. Naive O(n²) approach checks all pairs; divide-and-conquer achieves O(n log n) by recursively finding closest pairs in left/right halves and checking split pairs efficiently.
Karatsuba Multiplication
Fast multiplication algorithm for large integers using divide-and-conquer. Discovered by Anatoly Karatsuba in 1960, it was the first algorithm to demonstrate multiplication can be done faster than O(n²). Reduces three recursive multiplications instead of four, achieving O(n^log₂3) ≈ O(n^1.585) complexity.