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.
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
1interface Point {
2 x: number;
3 y: number;
4}
5
6function distance(p1: Point, p2: Point): number {
7 return Math.sqrt((p1.x - p2.x) ** 2 + (p1.y - p2.y) ** 2);
8}
9
10function closestPairBruteForce(points: Point[]): number {
11 let minDist = Infinity;
12 for (let i = 0; i < points.length; i++) {
13 for (let j = i + 1; j < points.length; j++) {
14 minDist = Math.min(minDist, distance(points[i], points[j]));
15 }
16 }
17 return minDist;
18}
19
20function closestPair(points: Point[]): number {
21 // Sort by x-coordinate
22 points.sort((a, b) => a.x - b.x);
23 return closestPairRec(points);
24}
25
26function closestPairRec(points: Point[]): number {
27 if (points.length <= 3) {
28 return closestPairBruteForce(points);
29 }
30
31 const mid = Math.floor(points.length / 2);
32 const midPoint = points[mid];
33
34 const leftMin = closestPairRec(points.slice(0, mid));
35 const rightMin = closestPairRec(points.slice(mid));
36
37 const delta = Math.min(leftMin, rightMin);
38
39 // Find points within delta of dividing line
40 const strip = points.filter(p => Math.abs(p.x - midPoint.x) < delta);
41 strip.sort((a, b) => a.y - b.y);
42
43 // Check split pairs
44 let splitMin = delta;
45 for (let i = 0; i < strip.length; i++) {
46 for (let j = i + 1; j < strip.length && (strip[j].y - strip[i].y) < delta; j++) {
47 splitMin = Math.min(splitMin, distance(strip[i], strip[j]));
48 }
49 }
50
51 return splitMin;
52}Deep Dive
Theoretical Foundation
Algorithm divides points by x-coordinate, recursively finds closest pairs in left and right halves, then checks pairs spanning the dividing line. Key insight: only need to check points within δ distance (minimum from recursive calls) of dividing line, and for each point, only check next 7 points when sorted by y-coordinate.
Complexity
Time
O(n log n)
O(n log n)
O(n log n)
Space
O(n)
Applications
Industry Use
Computational geometry and GIS systems
Computer graphics (collision detection)
Astronomy (finding close star pairs)
Molecular dynamics simulations
Machine learning (nearest neighbor algorithms)
Network analysis (finding closest nodes)
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.
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.
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.