13.6.3. Scanning Points

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 chunk introduces the closest pair of points problem, which is a common geometric problem. The main objective is to find two points in a given set that are closest to each other. This problem can be computationally demanding, especially as the number of points increases.

Imagine you are at a concert with many friends scattered around. You want to find out which two friends are standing closest together so you can join them. Calculating this manually can be tedious, especially if you have to check each friend against every other friend.

A naive algorithm could be to explicitly compute the distance between every pair of these n objects, which should be an order n squared algorithm. So, what we are going to see is that we can actually use divide and conquer and produce an order n log n algorithm for this problem.

The naive approach involves computing distances between each possible pair of points, resulting in a time complexity of O(n²). This means for each point, you compare it with every other point, leading to many calculations. The efficient approach using divide and conquer reduces this complexity significantly to O(n log n), making it feasible to handle larger data sets.

Think of searching for the shortest path in a city. A naive method would be to check every possible road (O(n²)), which could take forever. Instead, using maps and sorting routes allows you to find the best path much quicker (O(n log n)).

Each point is given by an x,y coordinate and we are using the usual utility and motion of distance that is the distance given by Pythagorean formula.

In this problem, we define points in a 2D plane using (x, y) coordinates. The distance between any two points is determined using the Pythagorean theorem, which states that the distance d between two points (x1, y1) and (x2, y2) can be computed as √((x2 - x1)² + (y2 - y1)²). This mathematical concept provides the basis for calculating distances in our algorithm.

Imagine plotting your friends' locations on a map. The Pythagorean theorem helps you measure the straight-line distance between two points, just as you would measure how far apart two places are on a map.

So, 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.

The key to the divide and conquer strategy in finding the closest pair of points is to split the set into two subsets. This is typically done by drawing a vertical line through the set of points, dividing it into left and right halves. Each of these halves is then processed recursively to find the closest pairs within them. This organization allows the algorithm to simplify the problem into manageable parts.

Consider splitting a large group of party-goers into two smaller groups based on their positions in a room. By addressing each group separately, you can more efficiently determine which two individuals in your original group are closest.

This does not tell us anything about distances between points on the left and points on the right and they could very well be points very close to each other across the boundary.

While each half is analyzed for the closest points within itself, there could still be pairs of points that lie across the dividing line that are closer than any pairs found within each subset. This necessitates checking distances between points that are close to the boundary of the dividing line.

Imagine a fence splitting two groups of friends at a park. Even though they’re in different areas, there could be two friends near the fence who are closer to each other than friends within the same area, requiring you to check across the fence.

Given points P, we will compute points, the set of points we will compute two sorted orders. So we will first scan these points by x coordinate from left to right and we will list them in this order.

To facilitate the divide and conquer strategy, we sort the points in two ways: by x-coordinates and y-coordinates. Sorting allows for a more efficient search for the closest point pairs, as points will be organized, making it easier to eliminate possibilities that are not worth considering.

Imagine sorting books on a shelf first by genre and then by the author's name. This method makes it easier to find a specific book quickly compared to having the books jumbled together.

Now we have to worry about how to combine them, how to take care of these points whose distance spans the interval, the line separating the two halves.

After solving for the closest points in each subset, the next step is to determine if there are any closer pairs that cross the dividing line. This step is crucial as the closest points may not necessarily be the nearest points within each subset but rather those that span across both subsets. Hence, a careful examination of points within a certain distance from the dividing line is necessary.

If you're trying to find the two closest friends at a party, checking within their respective circles might not be enough, as they might actually be closest if you consider those who are near the edge of both groups.

--