13.2.4. Brute Force Solution

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 solution involves checking every possible pair of points to determine which two points are closest to each other. Given 'n' points, this method would require calculating the distance for every combination of two points, which leads to a total of n(n-1)/2 comparisons. Since constants are disregarded in Big-O notation, this results in a time complexity of O(n²).

Imagine you have a group of friends at a party, and you want to find out which two friends are standing the closest together. You could go to each friend, measure how far away they are from every other friend, and keep track of the closest pair. This process would take a lot of time, especially if the party is large, just like the brute force approach is time-consuming for a large number of points.

So, let us see first the same problem if we had only one dimensional points. If we have one dimensional points then all these points lie along the line, which we can assume this the x axis. ... So, here the algorithm is n log n, because it takes n log n times to sort the points in x coordinate, after that finding the minimum is actually very easy.

In one dimension, finding the closest pair is considerably simpler. By sorting the points based on their coordinates, you can easily determine that the closest point to any given point is one of its adjacent neighbors. This sorting step takes O(n log n) time, and scanning through pairs of adjacent points takes O(n) time, leading to an overall efficient solution compared to the brute force method.

Think of a row of houses along a street. To find the two houses that are closest together, you could first sort them based on their addresses. After sorting, it's much easier to see that the closest two houses must be next to each other on that sorted list.

So, the challenge is to solve it in two dimensions. ... But, 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.

While it's simpler in one dimension, solving the closest pair problem in two dimensions introduces complexity. After dividing the points into two halves, you could have points from different sides that are closer to each other than any points on the same side. The brute force method fails to account for these cross-boundary pairs unless you check all combinations, leading to inefficiency.

Imagine a city divided by a river. If we consider houses on either side as points, just because you find the closest two houses on one side doesn’t mean they are the closest overall. There might be a pair of houses directly across the river that are even closer together, showcasing the limitation of only checking one side.

So, we will make the further step before we do this thing recursively. Given a points P we will compute points, the set of points ... and assume that we have done this of course, we can do this we know in order n log n time right to the beginning.

To apply the divide and conquer method effectively, points need to be sorted, which is done both by x and y coordinates. This step is crucial as it allows for efficient partitioning of points into two halves and simplifies the search for the closest pair across the boundaries. Sorting both dimensions takes O(n log n) time, a necessary upfront cost for the recursive algorithm that follows.

Think of organizing a library. Before you can easily find the closest books to one another, you must first sort the books by author's name and genre. This initial step helps when you want to separate them into sections and find pairs that might belong together.

--