13.1.1. Divide and Conquer: Closest Pair of 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.

The closest pair problem asks us to find the two points that are nearest to each other within a given set of points in a two-dimensional space. This problem is relevant in various fields, such as computer graphics, robotics, and geographical mapping, where it’s important to quickly find proximity between points.

Imagine you are in a city with many landmarks (points) and you need to find out which two landmarks are closest together. This could help in planning a walking route or locating nearby attractions.

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 method involves calculating the distance between each possible pair of points, leading to an inefficient O(n²) complexity. This means for large sets of points, the computation becomes exponentially tedious. Using the divide and conquer technique optimally reduces this complexity to O(n log n) by breaking down the problem into smaller, more manageable parts.

Think of it like organizing a huge library. Instead of checking every book one by one for a specific genre (the naive method), you could categorize the books by genre first and then look through each category—this is much quicker.

So, formally we are looking at points in two dimensions... distance given by Pythagoras used formula.

To find the distance between two points (p1, p2) in a two-dimensional plane, we can use the formula derived from Pythagorean theorem: √((x2 - x1)² + (y2 - y1)²). This formula allows us to compute the straight line distance (Euclidean distance) between two points represented by their coordinates.

Imagine you are trying to find the shortest path between two cities on a map. The distance formula is like the straight line (or crow's flight) distance, helping you gauge how far apart they are regardless of the roads in between.

So, we need to separate them based on their positions... split this set not by some arbitrary line like this, but rather we will try and split it by a vertical line.

Before applying the divide and conquer approach, we sort the points based on their x-coordinates. This step allows us to easily split the list into two halves, paving the way for recursive exploration of closest pairs. The idea is to use a vertical line to partition the point set into left and right segments to tackle them separately.

Imagine you have a group of children playing on a playground arranged loosely. Instead of just grabbing them at random to form two teams, you line them up according to their height (x-coordinates) and split them in half—this makes organizing them much simpler.

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.

Once we’ve computed the closest distances in both halves, we need to check for pairwise distances across the boundary line. This is crucial, as it's possible that the closest pair might consist of one point from each half. Therefore, we examine points around the dividing line within a certain range to ensure we don’t miss any potential closest pairs.

Returning to the playground analogy, after forming two teams based on height, you’d want to check if any of the tallest kids from one team is closer to any short kids from the other team. Just because they’re not on the same side doesn’t mean they aren’t the best match!

The claim is that if you look at this zone here which is plus minus d distance away from the separated line... therefore, we only need to consider points inside the zone.

When considering distances around the border, we limit our search to a band that extends d distance on either side of the vertical line separating the two halves. This allows us to focus only on potentially close points, which simplifies our comparisons significantly.

It's like attending a fair where the rides are split into two areas. You don’t need to consider rides in completely different sections if you're only looking for the ones closest to you; instead, you only check the rides within a short walking distance.

So, we have a non recursive part which is to first compute the initial sort it list P x and P y, this takes order on n log n time force.

The final algorithm combines sorting the list of points by both x and y coordinates and uses recursive calls to solve for the closest pairs in each half. The complexity of the entire algorithm is O(n log n), maintaining efficiency throughout its operations.

Imagine baking a complex cake. First, you sort your ingredients (the initial sort), then you follow the recipe step by step (the recursive calls) to create a cake that not only looks good but tastes great—efficiently using time and effort.

--