onenoughtone

Closest Pair of Points Pattern

What is the Closest Pair of Points Problem?

The Closest Pair of Points problem asks us to find the pair of points with the smallest distance between them in a set of points in a plane.

While this can be solved in O(n²) time using a brute force approach, divide and conquer allows us to solve it in O(n log n) time.

Key Steps

Sort Points: Sort all points by their x-coordinates
Divide: Split the points into two equal halves by a vertical line
Conquer: Recursively find the closest pairs in each half
Combine: Find the closest pair that spans the dividing line and compare with the closest pairs from each half

Implementation

Here's an implementation of the closest pair of points algorithm:

Time and Space Complexity

Time Complexity:

O(n log n), where n is the number of points.

Space Complexity:

O(n) for storing the points and the strip.

Key Insight: The Strip

The key insight in this algorithm is that we only need to check points that are within the minimum distance (found so far) of the dividing line.

Furthermore, for each point in the strip, we only need to check at most 7 points ahead of it (when sorted by y-coordinate). This is because any other points would be farther than the minimum distance we've already found.

This optimization reduces the combine step from O(n²) to O(n), resulting in an overall time complexity of O(n log n).

Previous Next

Pattern 3: Closest Pair of Points

Learn the geometric pattern of divide and conquer through the closest pair of points algorithm.

What is the Closest Pair of Points Problem?

The Closest Pair of Points problem asks us to find the pair of points with the smallest distance between them in a set of points in a plane.

While this can be solved in O(n²) time using a brute force approach, divide and conquer allows us to solve it in O(n log n) time.

Example:

Input: [(1,1), (2,3), (3,4), (4,2), (5,7)]

Output: The closest pair is (2,3) and (3,4) with distance √2 ≈ 1.414

Explanation: The Euclidean distance between (2,3) and (3,4) is √((3-2)² + (4-3)²) = √2, which is the smallest among all pairs.

Why Divide and Conquer?

Brute Force Approach

The brute force approach compares every pair of points, requiring O(n²) comparisons. This becomes inefficient for large datasets.

Divide and Conquer Advantage

By dividing the plane into two halves and recursively finding the closest pairs in each half, we can reduce the time complexity to O(n log n).

Key Insight

The key insight is that we only need to check points that are within the minimum distance (found so far) of the dividing line, and for each such point, we only need to check a constant number of nearby points.

The Four Steps of the Algorithm

1Sort Points

Sort all points by their x-coordinates. This takes O(n log n) time.

2Divide

Split the points into two equal halves by a vertical line through the median x-coordinate.

3Conquer

Recursively find the closest pairs in the left and right halves. Let the minimum distance found be δ.

4Combine

Find the closest pair that spans the dividing line and has distance less than δ. Return the minimum of this distance and δ.

Implementation

Here's an implementation of the closest pair of points algorithm:

closestPair.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
function closestPair(points) {
  // Sort points by x-coordinate
  points.sort((a, b) => a.x - b.x);
  
  // Find the closest pair recursively
  return closestPairRecursive(points, 0, points.length - 1);
}
 
function closestPairRecursive(points, start, end) {
  // Base case: If there are 2 or 3 points, solve by brute force
  if (end - start <= 2) {
    return bruteForceClosestPair(points, start, end);
  }
  
  // Divide: Find the middle point
  const mid = Math.floor((start + end) / 2);
  const midPoint = points[mid];
  
  // Conquer: Recursively find the closest pairs in left and right halves
  const leftClosest = closestPairRecursive(points, start, mid);
  const rightClosest = closestPairRecursive(points, mid + 1, end);
  
  // Find the minimum distance from left and right halves
  let minDist = Math.min(leftClosest.distance, rightClosest.distance);
  let closestPair = leftClosest.distance <= rightClosest.distance ? leftClosest : rightClosest;
  
  // Combine: Check if there's a closer pair that spans the dividing line
  const strip = [];
  
  // Collect points that are within minDist of the dividing line
  for (let i = start; i <= end; i++) {
    if (Math.abs(points[i].x - midPoint.x) < minDist) {
      strip.push(points[i]);
    }
  }
  
  // Sort the strip by y-coordinate
  strip.sort((a, b) => a.y - b.y);
  
  // Check each point in the strip and compare it with at most 7 points ahead
  for (let i = 0; i < strip.length; i++) {
    for (let j = i + 1; j < strip.length && j - i < 8; j++) {
      const dist = distance(strip[i], strip[j]);
      if (dist < minDist) {
        minDist = dist;
        closestPair = { point1: strip[i], point2: strip[j], distance: dist };
      }
    }
  }
  
  return closestPair;
}
 
function bruteForceClosestPair(points, start, end) {
  let minDist = Infinity;
  let closestPair = null;
  
  for (let i = start; i <= end; i++) {
    for (let j = i + 1; j <= end; j++) {
      const dist = distance(points[i], points[j]);
      if (dist < minDist) {
        minDist = dist;
        closestPair = { point1: points[i], point2: points[j], distance: dist };
      }
    }
  }
  
  return closestPair;
}
 
function distance(p1, p2) {
  return Math.sqrt(Math.pow(p1.x - p2.x, 2) + Math.pow(p1.y - p2.y, 2));
}

Key Insight: The most critical part of the algorithm is the combine step, where we check if there's a closer pair that spans the dividing line. We only need to consider points that are within δ of the dividing line, and for each such point, we only need to check at most 7 points ahead of it when sorted by y-coordinate.

Time and Space Complexity

Time Complexity

O(n log n), where n is the number of points.

Explanation: The initial sorting takes O(n log n) time. The recurrence relation for the divide and conquer algorithm is T(n) = 2T(n/2) + O(n), which resolves to O(n log n) using the Master Theorem.

Space Complexity

O(n) for storing the points and the strip.

Explanation: We need O(n) space to store the input points and the strip of points near the dividing line. The recursion stack uses O(log n) space, but the O(n) term dominates.

The Strip Optimization

The key to the efficiency of this algorithm is the strip optimization in the combine step:

Why the Strip Works

After finding the minimum distance δ from the left and right halves, we only need to check points that are within δ of the dividing line. Any pair of points farther from the line than δ cannot be closer than the pairs we've already found.

The 7-Point Rule

For each point in the strip, we only need to check at most 7 points ahead of it (when sorted by y-coordinate). This is because any other points would be farther than δ. This reduces the combine step from O(n²) to O(n).

Applications and Variations

Collision Detection

Used in physics simulations and video games to detect when objects are about to collide.

Example: Detecting when particles in a simulation come too close to each other.

Clustering

Finding groups of points that are close to each other in data mining and machine learning.

Example: Identifying clusters of similar customers in marketing data.

Higher Dimensions

The algorithm can be extended to work in higher dimensions, though with increased complexity.

Example: Finding the closest pair of points in 3D space for virtual reality applications.

Dynamic Version

Maintaining the closest pair as points are added or removed from the set.

Example: Tracking the closest pair of moving objects in real-time.

Previous: Quick Sort Pattern Next: Strassen's Matrix Multiplication

Intro Visualize Patterns Practice

onenoughtone

Back to Home

onenoughtone

Back to Home

Closest Pair of Points Pattern

What is the Closest Pair of Points Problem?

The Closest Pair of Points problem asks us to find the pair of points with the smallest distance between them in a set of points in a plane.

While this can be solved in O(n²) time using a brute force approach, divide and conquer allows us to solve it in O(n log n) time.

Key Steps

Sort Points: Sort all points by their x-coordinates
Divide: Split the points into two equal halves by a vertical line
Conquer: Recursively find the closest pairs in each half
Combine: Find the closest pair that spans the dividing line and compare with the closest pairs from each half

Implementation

Here's an implementation of the closest pair of points algorithm:

Time and Space Complexity

Time Complexity:

O(n log n), where n is the number of points.

Space Complexity:

O(n) for storing the points and the strip.

Key Insight: The Strip

The key insight in this algorithm is that we only need to check points that are within the minimum distance (found so far) of the dividing line.

This optimization reduces the combine step from O(n²) to O(n), resulting in an overall time complexity of O(n log n).

Previous Next

Pattern 3: Closest Pair of Points

Learn the geometric pattern of divide and conquer through the closest pair of points algorithm.

What is the Closest Pair of Points Problem?

The Closest Pair of Points problem asks us to find the pair of points with the smallest distance between them in a set of points in a plane.

While this can be solved in O(n²) time using a brute force approach, divide and conquer allows us to solve it in O(n log n) time.

Example:

Input: [(1,1), (2,3), (3,4), (4,2), (5,7)]

Output: The closest pair is (2,3) and (3,4) with distance √2 ≈ 1.414

Explanation: The Euclidean distance between (2,3) and (3,4) is √((3-2)² + (4-3)²) = √2, which is the smallest among all pairs.

Why Divide and Conquer?

Brute Force Approach

The brute force approach compares every pair of points, requiring O(n²) comparisons. This becomes inefficient for large datasets.

Divide and Conquer Advantage

By dividing the plane into two halves and recursively finding the closest pairs in each half, we can reduce the time complexity to O(n log n).

Key Insight

The Four Steps of the Algorithm

1Sort Points

Sort all points by their x-coordinates. This takes O(n log n) time.

2Divide

Split the points into two equal halves by a vertical line through the median x-coordinate.

3Conquer

Recursively find the closest pairs in the left and right halves. Let the minimum distance found be δ.

4Combine

Find the closest pair that spans the dividing line and has distance less than δ. Return the minimum of this distance and δ.

Implementation

Here's an implementation of the closest pair of points algorithm:

closestPair.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
function closestPair(points) {
  // Sort points by x-coordinate
  points.sort((a, b) => a.x - b.x);
  
  // Find the closest pair recursively
  return closestPairRecursive(points, 0, points.length - 1);
}
 
function closestPairRecursive(points, start, end) {
  // Base case: If there are 2 or 3 points, solve by brute force
  if (end - start <= 2) {
    return bruteForceClosestPair(points, start, end);
  }
  
  // Divide: Find the middle point
  const mid = Math.floor((start + end) / 2);
  const midPoint = points[mid];
  
  // Conquer: Recursively find the closest pairs in left and right halves
  const leftClosest = closestPairRecursive(points, start, mid);
  const rightClosest = closestPairRecursive(points, mid + 1, end);
  
  // Find the minimum distance from left and right halves
  let minDist = Math.min(leftClosest.distance, rightClosest.distance);
  let closestPair = leftClosest.distance <= rightClosest.distance ? leftClosest : rightClosest;
  
  // Combine: Check if there's a closer pair that spans the dividing line
  const strip = [];
  
  // Collect points that are within minDist of the dividing line
  for (let i = start; i <= end; i++) {
    if (Math.abs(points[i].x - midPoint.x) < minDist) {
      strip.push(points[i]);
    }
  }
  
  // Sort the strip by y-coordinate
  strip.sort((a, b) => a.y - b.y);
  
  // Check each point in the strip and compare it with at most 7 points ahead
  for (let i = 0; i < strip.length; i++) {
    for (let j = i + 1; j < strip.length && j - i < 8; j++) {
      const dist = distance(strip[i], strip[j]);
      if (dist < minDist) {
        minDist = dist;
        closestPair = { point1: strip[i], point2: strip[j], distance: dist };
      }
    }
  }
  
  return closestPair;
}
 
function bruteForceClosestPair(points, start, end) {
  let minDist = Infinity;
  let closestPair = null;
  
  for (let i = start; i <= end; i++) {
    for (let j = i + 1; j <= end; j++) {
      const dist = distance(points[i], points[j]);
      if (dist < minDist) {
        minDist = dist;
        closestPair = { point1: points[i], point2: points[j], distance: dist };
      }
    }
  }
  
  return closestPair;
}
 
function distance(p1, p2) {
  return Math.sqrt(Math.pow(p1.x - p2.x, 2) + Math.pow(p1.y - p2.y, 2));
}

Time and Space Complexity

Time Complexity

O(n log n), where n is the number of points.

Space Complexity

O(n) for storing the points and the strip.

Explanation: We need O(n) space to store the input points and the strip of points near the dividing line. The recursion stack uses O(log n) space, but the O(n) term dominates.

The Strip Optimization

The key to the efficiency of this algorithm is the strip optimization in the combine step:

Why the Strip Works

The 7-Point Rule

Applications and Variations

Collision Detection

Used in physics simulations and video games to detect when objects are about to collide.

Example: Detecting when particles in a simulation come too close to each other.

Clustering

Finding groups of points that are close to each other in data mining and machine learning.

Example: Identifying clusters of similar customers in marketing data.

Higher Dimensions

The algorithm can be extended to work in higher dimensions, though with increased complexity.

Example: Finding the closest pair of points in 3D space for virtual reality applications.

Dynamic Version

Maintaining the closest pair as points are added or removed from the set.

Example: Tracking the closest pair of moving objects in real-time.

Previous: Quick Sort Pattern Next: Strassen's Matrix Multiplication