13.2.1. Naive Algorithm

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 a geometric problem, specifically how to find the closest pair of points in a given set of points using a divide and conquer algorithm. It highlights the significance of this problem in fields such as computer graphics or gaming where finding the closest objects can enhance user experience. The section sets the stage for exploring how traditional methods might be inefficient, prompting the need for better algorithmic strategies.

Imagine you are playing a video game with multiple characters displayed on the screen. To optimize gameplay, the system needs to quickly determine which character is closest to another, allowing for interactions and better navigation. This serves as a practical illustration of the importance of efficiently finding the closest pair of points.

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.

Here, the naive approach to solving the problem is described, which involves calculating the distance between every possible pair of points. Since the number of pairs increases quadratically with the number of points (n), this results in a time complexity of O(n²). The inefficiency of this method is a critical point, as it can become impractical for large sets of points, leading to the search for a more optimized approach.

Suppose you have a list of 100 friends, and you want to see who is the closest friend based on GPS coordinates. If you compare every friend's location with every other friend's location, you'll need to perform 4,950 calculations (which is almost 100 squared). This slow method can become cumbersome, especially as your network grows.

We will be using the usual utility and motion of distance that is the distance given by Pythagoras used formula, which is that the distance between p1 and p2 is the square root of (x2 - x1)² + (y2 - y1)².

In this chunk, the Pythagorean theorem is referenced as the method for calculating the distance between two points in a 2D space, defined by their coordinates. This formula is central to the algorithm as it forms the basis for evaluating the distances between pairs of points.

Think of a map where each friend’s house is marked with a coordinate. To find out how far away one friend lives from another, you can use this formula, treating their respective homes as coordinates on the map, much like finding the shortest path in a city.

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.

This chunk discusses an important assumption made for the algorithm's analysis: that all x and y coordinates of the points are distinct. This simplifies the complexity of the problem, though it is noted that the algorithm can be adapted to handle cases where this is not true.

Imagine organizing a race where each participant runs on a unique lane. If each lane is labeled with a unique number, it makes it easier to track their progress. Similarly, the assumption of unique coordinates helps in efficiently determining distances among points.

The brute force solution would be to try every pair, compute d(p_i, p_j) and then report the minimum amount of distances. So, this would be an order n squared algorithm.

This chunk reiterates the brute force or naive approach where every possible pair distance is calculated. While straightforward, it emphasizes the inefficiency tied to its O(n²) complexity, urging students to seek optimized solutions like those provided by divide and conquer techniques.

Using the earlier example, if you have to compare every friend with every other friend to find the closest one, the time taken can be overwhelming as the number of friends increases. This example underscores why a faster, more sophisticated method is desirable.

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 is the x-axis.

Here, the section introduces a simplified version of the problem, focusing on one-dimensional points. It encourages students to consider how the problem's dimensionality affects its complexity and the solution approach. By simplifying to one dimension, it sets the groundwork for understanding how to manage more complex two-dimensional scenarios.

Imagine you’re at a race track where all participants are running along a straight path. To find the closest runner, you just need to check the gaps between each runner, making it much simpler than if they were spread out on a field.

--