13.6.1. Base Case for Recursion

We now look at another divide and conquer algorithm, this is the geometric problem, given a set of points we would like to compute the closest pair of points among them.

This introduction sets the stage for exploring a problem in computational geometry called the 'closest pair of points.' It establishes that we are seeking to find the pair of points that are closest to each other within a given set of points, a problem that can be tackled using the divide and conquer method.

Imagine playing a video game where multiple objects are displayed on the screen. At any moment, you might want to identify which two objects are closest to each other. This scenario mirrors the problem of finding the closest pair of points among a set.

A brute force solution would be to try every pair, compute d of p i p j and then report the minimum amount of distances. So, this would be an order n squared algorithm.

The brute force approach involves checking every possible pair of points, calculating the distance for each, and keeping track of the minimum distance found. This method, while straightforward, is inefficient for large datasets because the time complexity is quadratic (O(n^2)), meaning that if you double the number of points, the computation roughly quadruples.

Think about finding the shortest path in a city by examining every possible route between each pair of locations. This method might work for a few streets, but as the number of streets increases, it quickly becomes overwhelming and impractical.

If we have one dimensional points then all these points lie along the line, which we can assume this is the x axis. We can first sort them, so that we have the points in increasing order of x coordinate and then it is easy to see that the distances that we need are the distances between two adjacent points.

When dealing with points in one dimension, sorting them simplifies the problem significantly. Once sorted, the closest pair of points will always be adjacent. By only checking the distances between neighboring points, the algorithm runs much more efficiently with a time complexity of O(n log n) due to sorting.

Imagine you're looking for the closest two houses on a street. If you arrange the houses in order from left to right, you only need to check the gaps between each pair of neighboring houses instead of every house against every other house.

In two dimensions if we are going to use divide and conquer, we need a way of separating the points into two groups, a roughly equal size or a hopefully exactly equal size.

In two dimensions, the divide and conquer strategy involves dividing the set of points into two groups, ideally of equal size. This can be done by drawing a vertical line through the points. After dividing the points, the algorithm recursively finds the closest pairs in both divided groups. However, it's crucial to also check the pairs that span across the dividing line since they might be closer than pairs within the same group.

Think of it like splitting a crowd of people into two sections for a dance competition. While you can judge each side separately, you must also check for best dancers who might exist at the dividing line between the two groups.

So, we only need to consider points across the separator which line within this plus minus d, any pair outside this cannot be the closest pair of the line.

After determining the closest pairs within each divided group, we only need to consider points that are located within a certain distance (d) from the dividing line. If a point is further away than this distance, its closest pair cannot cross the dividing line and therefore cannot be the overall closest pair. This reduces the number of potential pairs to check significantly.

Imagine you have a set of sprinting tracks divided by a narrow field. Only those runners close to the edge of the field on either side need to be compared for their potential closeness because those further away will not influence the closest overlap.

--