13.4.1. Dividing 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 section introduces the problem of finding the closest pair of points in a two-dimensional space using a divide and conquer method. It establishes the context by mentioning the relevance of this problem in applications like video games, where identifying the closest objects on-screen is important.

Imagine you're playing a video game with multiple characters on the screen. If the game needs to determine which character is nearest to you at any given moment, efficiently finding that closest character is critical to gameplay. This section highlights how algorithms can solve such problems effectively.

The naive algorithm could be to explicitly compute the distance between every pair of these n objects, which should be an order n squared algorithm.

This part describes the brute-force approach to the problem, where every possible pair of points is compared to calculate their distances, leading to a time complexity of O(n²). This method is inefficient for large datasets, prompting the need for a more efficient algorithm.

Consider trying to find the closest friend in a large room by asking each one for their exact distance from you. If there are 10 friends, you'd have to ask 45 pairs (10 choose 2). Now imagine having to do this for 100 friends: it quickly becomes unmanageable!

We are using the usual utility and motion of distance...the distance between p 1 and p 2 is the square root of (x2 - x1)² + (y2 - y1)².

In this chunk, the text introduces the distance formula derived from the Pythagorean theorem, which will be utilized to compute the distances between points. Every point is defined by its coordinates (x, y), and this formula provides a mathematical foundation for measuring distances in two-dimensional space.

Think of the distance formula as measuring the straight-line path between two cities on a map. The coordinates of each city can be plotted, and using the distance formula allows you to find how far apart they are as the crow flies, rather than taking a winding road.

Our target is given a set of n points p 1 to p n to find the closest pair among them...no two points in this set have the same x or y coordinate.

The text sets up an assumption for the algorithm: no two points will share the same x or y coordinate. This simplifies the algorithm and ensures clarity in identifying the closest pair. While the algorithm can be generalized to handle cases with overlapping coordinates, doing so introduces unnecessary complication.

Imagine a race track where each competitor (point) has a unique starting line. If two competitors started from the same line, it would create confusion. Setting the rule that no two racers start at the same point simplifies the race—everyone has a clear, defined position.

If we have one dimensional points then all these points lie along the line, which we can assume is the x-axis. So, we have a bunch of points and we want to find the closest point.

In one dimension, finding the closest point is straightforward. By sorting the points along the x-axis, the closest pair can be identified by simply calculating the distances between adjacent points, leading to a much more efficient O(n log n) algorithm due to the sorting step.

Think of standing in a line with friends, and you only need to ask the person next to you how far apart you are. Since you’re all lined up, you don't need to check everyone independently; just looking at your immediate neighbors saves time.

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.

Transitioning to two dimensions, the problem becomes more complex. The method of dividing the points effectively is crucial. By using a vertical line to split the points into two groups, the algorithm can then recursively apply itself to find the closest pairs within each group, but special attention must be paid to points near the dividing line.

Imagine trying to organize a mixed bag of colored marbles into two separate containers. If you don't separate them correctly, you might miss the closest match between the containers! Like this, ensuring an effective division is crucial for finding the closest marbles in two dimensions.

Given points P we will compute points, the set of points we will compute two sorted orders... and call this P_x and P_y.

The recursive nature of the algorithm is pushed forth here. After sorting the points into two separate lists organized by x and y coordinates, the algorithm divides the problem into smaller parts, and then these results must be combined effectively to address potential closest pairs that straddle the dividing line.

Imagine organizing a huge puzzle. If you solve one section and another independently, you still need to fit those sections together. This is like combining the results from the left and right groups after they’ve been sorted—ensuring they connect correctly is just as vital.

If we solve this problem on the left among all the points in Q, I will identify some pair of points as being the nearest pair with the distance d_Q.

After recursively finding the closest pairs in both halves of the point set, the algorithm must evaluate the candidates that may exist across the dividing line. The closest distance found within the two halves is compared alongside pairs present in a particular zone surrounding the dividing line, filtering out any points that are too distant to be valid candidates for the closest distance.

Think of a detective searching for the closest suspects among different neighborhoods. After checking two areas (right and left), the detective also needs to consider suspects that might be near the boundary between the two areas to ensure they don’t miss a crucial lead.

--