13.7.2. Overall Complexity

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 problem of finding the closest pair of points in a set using a divide and conquer algorithm. The objective is to identify two points from a given set that are nearest to each other in terms of distance. This problem is fundamental in computational geometry and has various applications, such as in computer graphics and gaming.

Think of a map with several landmarks. For example, if you have a bunch of restaurant locations on a city map, finding the two restaurants that are closest to each other quickly can help you decide where to eat based on proximity.

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 to find the closest pair of points requires calculating the distance between every possible pair of points. This results in a time complexity of O(n²), which is inefficient for large datasets. The efficient approach proposed in this section describes a divide and conquer method that reduces this time complexity to O(n log n) by breaking the problem down into smaller subproblems.

Imagine trying to find the quickest route between several towns by checking every possible road connection (naive). It would take a long time. Instead, if you divide the towns into regions and only check the nearest towns in each region, comparing borders when necessary can help you find the quickest route much faster.

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 Pythagorean formula.

In this chunk, the text establishes that the points under consideration are in two-dimensional space, represented by x and y coordinates. The Pythagorean theorem gives the formula required to compute the distance between any two points, which assists in determining the closest pair during calculations.

Visualize points as locations on a 2D grid, like a chessboard, where each square corresponds to a coordinate. The formula helps you figure out how far apart two squares are, which is essential if you want to determine which two squares (or locations) are closest together.

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 involves systematically checking the distance between every possible pair of points. This results in significant computation, specifically quadratic time complexity due to the need to check n*(n-1)/2 pairs, making it impractical for larger datasets.

Consider trying to find a missing item among 100 boxes by checking each box one by one against every other box. It takes a long time to do this, especially if many boxes could be sorted in a way that allows you to quickly locate the missing item instead of searching each pair exhaustively.

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

To apply the divide and conquer strategy effectively in two dimensions, points must be separated into two groups of roughly equal size. A vertical line is drawn to help categorize these groups so that the algorithm can process them individually but in parallel.

Imagine sorting all the fruits in a mixed basket by placing them into two bins based on type. Once sorted, you can examine each bin separately to find the best quality fruit in each, which is more efficient than checking each fruit one by one.

But, this does not tell us anything about distances between points on the left and points on the right...

Dividing the points does not inherently capture distances between points that are across the dividing line, which is essential in identifying the closest pair. As a result, additional checks must be conducted for pairs that bridge the dividing line to ensure that no closer pair is missed.

If you have two groups of friends sitting in different rooms, you might sort them into two rooms to compare who's closest within each. But you should also ensure that people sitting on the boundary between rooms are compared against those from the opposite room since they might have a special connection.

We have this following algorithm, 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...

The algorithm effectively combines the steps for initially sorting the points into two sorted lists and recursively dealing with the closest pairs within each of these divisions. By taking advantage of both the sorted order of points and the divide and conquer method, the algorithm achieves an overall time complexity of O(n log n).

Imagine writing a detailed report where you first gather all your data (initial sort), categorize it into sections (divide), summarize each section separately (conquer), and then combine everything into a cohesive final report that is easy to follow!

--