Closest Pair of Points
Overview
The Closest Pair of Points solver finds the two points with minimum Euclidean distance using a divide-and-conquer algorithm. Watch as the algorithm recursively divides the point set and efficiently finds the closest pair in O(n log n) time. Perfect for understanding divide-and-conquer and geometric algorithms.
Tips
- Divide-and-conquer approach achieves O(n log n) time (vs naive O(n²))
- Divides points by x-coordinate, recursively solves subproblems
- Must check points near the dividing line (within distance δ)
- Only need to check 7 points in the strip for each point
- Applications: collision detection, clustering, nearest neighbor
- Visualization shows recursive divisions and strip checking
- The closest pair distance is highlighted in real-time