13.5.3. Points in the Zone

So, formally we are looking at points in two dimensions, so each point is given by an x y coordinate x p, y p and we are using the usual utility and motion of distance that is the distance given by Pythagoras used formula, which is that the distance between p 1 and p 2 is the square root of (x2 - x1)² + (y2 - y1)².

Here, we are introduced to the distance formula used to calculate the distance between two points in a two-dimensional space. Each point is represented by its coordinates (x, y). The formula comes from the Pythagorean theorem, where the distance between two points is the hypotenuse of a right triangle formed by the horizontal and vertical distances between the points.

Think of two cities on a map. Each city can be represented as a point with coordinates. The distance between these two cities can be imagined as the straight line you would draw on a map, which is exactly what the distance formula calculates.

So, as we have seen 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 to finding the closest pair of points involves calculating the distance between every possible pair of points, which results in a time complexity of O(n²). This means that if you double the number of points, you quadruple the number of calculations needed, making it inefficient for large datasets.

Imagine trying to find the nearest friend in a crowd by asking every single person around you about their closest friends. This approach gets exhausting quickly as more people arrive since every newcomer would require an additional round of questioning.

So, it 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. So, a natural way is to separate them based on their positions.

To optimize the search for the closest points, we can use the divide and conquer strategy. This involves dividing the set of points into two groups, ideally of equal size, which can then be processed separately. By focusing on smaller subsets, we can reduce the complexity significantly compared to checking all pairs in one go.

Think of looking for the nearest coffee shop. Instead of walking around the entire city, which would take a lot of time, you can first narrow it down to your neighborhood, then to your street, and finally choose among a few shops right next to each other.

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.

After dividing the points, we need to consider the closest distances not only within each group but also across the boundary between the two groups. This is critical because the closest pair might be located in different halves, so additional checks are necessary to account for those pairs.

Imagine you split a group of friends into two rooms at a party. While most of your best friends are in one room, your closest buddy might be in the other. If you don't check the other room, you might miss out on who is actually closest to you.

Given a 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 listed in this order and call it P x, then we will scan this, the list P from...

To efficiently manage our search for the closest points, we sort the points in two orders: by their x-coordinates and their y-coordinates. This step is crucial for optimizing the subsequent distance checks and helps us search the points quickly and effectively.

Sorting points is like organizing your desk. If you have all your stationery sorted by type (pens, pencils, erasers), it’s much easier and faster to find what you need rather than rummaging through a mixed pile.

So, when we do the recursive call, because we have P x sort it by x coordinate, we know that the line that we need to draw is the one that separates P x into two equal parts.

Once we have sorted the points, we make recursive calls to further split the data until we reach a manageable size. This step ensures that we continually divide our search into smaller parts, optimizing our calculations.

Recursive calls can be compared to a family tree. You start with one person and keep splitting the tree down to their children, then their grandchildren, and so on. Each generation helps you narrow down your search to specific relatives.

Now, we are interested in this smaller or these two, because the smaller are these two is a candidate for the overall minimum distance.

After finding the closest distances within the divided groups, we compare them to determine the overall smallest distance. This comparison allows for the identification of the closest pair across the entire set of points.

This is akin to racing to see which athlete can run the fastest. After running heats, you compare the best times to see who wins overall, rather than just looking at individual races.

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

We ascertain the closest pair from each subdivided group and label them with their respective minimum distances, which we will then compare. This helps us finalize the nearest pair of points overall as we take into account distances both within and across the boundary.

Think of it like a competition where the finalists from each round are compared to find the ultimate champion. Each round gives us a potential winner, but we must see which one outshines all others in the final.

--