Closest Pair of Points

The closest pair of points problem is a fundamental computational geometry problem: given n points in a plane, find the pair of points with the smallest Euclidean distance between them.

Brute Force Complexity: O(n²) - check all pairs

Divide-and-Conquer Complexity: O(n log n)

The algorithm uses a divide-and-conquer approach similar to merge sort:

1. Preprocessing: Sort all points by x-coordinate
2. Divide: Split the points into two halves by a vertical line
3. Conquer: Recursively find the closest pair in left and right halves
4. Combine: Check for pairs that span the dividing line
   • Only need to check points within δ distance from the dividing line
   • For each point, only check the next 7 points in the strip (sorted by y-coordinate)
5. Return: The minimum of the three distances found

When checking points near the dividing line, we don't need to check all pairs. Due to the geometry:

• We only check points within a strip of width 2δ (where δ is the current minimum distance)
• For each point in the strip, we only need to check at most 7 points ahead (sorted by y-coordinate)
• This is because no more than 8 points can fit in a δ × δ square while maintaining distance ≥ δ

This optimization is crucial for maintaining O(n log n) complexity.

• Geographic Information Systems (GIS): Finding nearest neighbors
• Computer Graphics: Collision detection and clustering
• Data Mining: Identifying similar data points
• Air Traffic Control: Detecting potential conflicts
• Molecular Biology: Finding similar protein structures
• Pattern Recognition: Feature matching and classification

• Add Points: Click anywhere on the canvas to add a point
• Generate Random: Click "Generate Random Points" to create a random set
• Visualize: Click "Visualize Algorithm" to see the divide-and-conquer process
• Clear: Click "Clear Canvas" to start over
• Options:
  • Show Partitions: Display left/right partitions during recursion
  • Show Steps: Display detailed algorithm steps
  • Animate Algorithm: Slow down visualization for better understanding

Time Complexity: O(n log n)

• Preprocessing (sorting): O(n log n)
• Recursive division: O(log n) levels
• Each level processes O(n) points
• Strip checking: O(n) per level due to the 7-point optimization

Space Complexity: O(n) for storing sorted arrays and recursion stack

This is significantly better than the brute force O(n²) approach, especially for large datasets.