13.3.1. Sorting and Finding Minimum Distance

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.

Here, we're introducing a geometric problem where we want to find the closest pair of points from a given set. This problem can be solved using a divide and conquer approach, which is a powerful algorithm design paradigm that divides the problem into smaller parts, solves each part, and combines the results.

Think of a large city where you want to find the two closest coffee shops. Instead of checking every possible coffee shop, you first split the city into neighborhoods, find the closest coffee shop pair within each neighborhood, and then check for any closer pairs that cross neighborhoods.

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.

The naive approach to finding the closest pair involves calculating the distance between every possible pair of points (for n points, this means n(n-1)/2 comparisons), leading to a time complexity of O(n^2). While this straightforward method is easy to implement, it's not efficient for larger datasets.

Imagine trying to find the closest friend in a crowd by asking each friend about their distance from every other friend—this would take a long time and is pretty inefficient.

We are using the usual utility and motion of distance that is the distance given by Pythagoras used formula.

To find the distance between any two points (p1 and p2), we apply the Pythagorean theorem. The distance is calculated as the square root of the sum of the squares of the differences in their x and y coordinates. This formula provides a convenient way to quantify how far apart the two points are in a two-dimensional space.

If you've ever used a map app, the direct distance between two points that the app computes is akin to applying this distance formula. It's figuring out how far apart two locations are, taking the straight line path into account.

It will be convenient for the analysis of the algorithm that we are going to suggest that no two points in this set have the same x or y coordinate.

To simplify the algorithm's analysis, we assume that all points have unique x and y coordinates. This assumption allows us to focus on the algorithm's mechanics without getting sidetracked by special cases where points may overlap. If necessary, the algorithm can be adjusted later to handle such cases.

Think about it like organizing a race—if every racer has a unique number on their jersey, it's easier to identify who is who. In the context of the points, unique coordinates help us avoid confusion.

So, let us see first the same problem if we had only one dimensional points.

If we reduce the problem to one-dimensional points along a line, the closest pair can easily be found by first sorting the points and then only comparing adjacent points. This greatly reduces the number of comparisons needed to find the closest pair, achieving a time complexity of O(n log n) due to the sorting step.

Imagine lining up a series of people according to their heights. Once sorted, to find the two closest heights, you'd only need to compare each person with the one next to them instead of checking everyone.

So, in two dimensions if we are going to use divide and conquer, we need a way of separating the points into two groups.

In two dimensions, we can employ the divide and conquer strategy by splitting the points with a vertical line, separating them into two groups of approximately equal size. This allows the algorithm to solve each half independently, but we must be careful to account for points that might be close to the dividing line, as they may form the closest pairs.

Consider dividing a huge park into two halves for a race. After the runners start from each half, you must check whether the fastest from each side are beating out runners near the center line.

We need to compute the closest pairs across the separating line and this is the challenge.

Once the points are divided and the closest distances within each side are computed, we need to check the potential closest pairs that straddle the dividing line. This involves examining points within a certain distance from the line, as they may yield a closer distance than both sides.

In the context of the park race, although most runners are divided into two groups for easier management, those on the edge of the dividing line might just be the fastest, and we have to check them closely!

Given a points P we will compute points, the set of points we will compute two sorted orders.

Before implementing the recursive calls, we also sort the points based on their y-coordinates. This sorting is crucial so that when we merge the results from the two groups, we can easily manage and find pairs of points that might be the closest.

Imagine sorting a pile of mail first by the recipient's address in alphabetical order, and then by the timestamps on their letters. It makes retrieving each letter more organized and efficient.

In order to continue this recursion I need to assume that Q is sorted in both x and y.

During the recursion, it's necessary to ensure both halves of the point sets (Q and R) remain sorted in terms of both x and y dimensions. By doing this, we can efficiently manage how we compare points and eliminate unnecessary checks.

Think of sorting a book collection by genre and then by author. Maintaining both sorts allows easier access to specific books without re-sorting them each time.

So, the claim is that if you look at this zone here which is plus minus d distance away from the separated line...

We derive a zone around the vertical dividing line and restrict our checks for the closest pair to points within this region only. The rationale is that any point beyond this zone wouldn’t yield a distance smaller than the closest pair found during the individual recursive checks.

It’s like trying to find the nearest exit in a building, knowing that the closest possible exit can only be found within a certain distance from your current location. Any exit further away won't help you.

So, we start with by assuming that we have set off a problem. So, that P has been split into two copies P x and P y sort it by x, sort it by y.

The algorithm concludes by recursively solving the closest pair problem for the two groups and merging those results with careful checks for points around the dividing line. This method leads to an efficient solution with a time complexity of O(n log n) due to the sorting and recursive divisions.

Think of assembling a puzzle—first, you separate the edge pieces from the others and work on each section independently. Finally, you merge the sections, making sure to connect the edges just right for a complete picture.

--