13.2.2. Distance Formula

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, which is that the distance between p1 and p2 is the square root of (x2 - x1)² + (y2 - y1)².

In two-dimensional space, every point can be represented by its coordinates (x, y). To find the distance between two points, we need to apply the Pythagorean Theorem. This theorem relates the lengths of the sides of a right triangle to the distance between two points. The formula states that the distance d between two points (x1, y1) and (x2, y2) is calculated as the square root of the sum of the squares of the differences in their coordinates: d = √((x2 - x1)² + (y2 - y1)²). This means you first find how far apart the x-coordinates are and how far apart the y-coordinates are, square both of those differences, add them together, and take the square root of that sum to get the direct distance between the points.

Imagine you are walking in a city laid out in a grid, just like a coordinate system. If you want to find the shortest path to your friend's house (point A) from yours (point B), you can either walk directly (the distance calculated by our formula) or walk along the streets, which may take longer. The formula essentially helps you find the quickest 'as-the-crow-flies' distance, representing the direct route.

Our target is given a set of n points p1 to pn to find the closest pair among them. It will be convenient for the analysis of the algorithm that no two points in this set have the same x or y coordinate.

In order to simplify our analysis of the algorithm that will identify the closest pair of points, we assume that all points are unique in terms of their coordinates. This means that no two points can have the same x-coordinate or y-coordinate. This assumption simplifies calculations, as we avoid complications that would arise from overlapping coordinates. In algorithms, unique inputs generally lead to clearer and more manageable outputs, which is especially important in geometric problems like this.

Think of this like organizing a race where each runner (point) has a unique bib number (coordinate). If two runners had the same number, it would create confusion about who is in the lead or finishing where. Having unique identifiers for each runner helps keep the event organized and clear, much like how unique coordinates help keep our algorithm efficient and straightforward.

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

The brute force method to find the closest pair of points involves checking every possible pair of points and calculating their distances using the distance formula. For n points, there are n(n-1)/2 pairs, which leads to a time complexity of O(n²). This method is straightforward but inefficient, especially as the number of points increases. Fortunately, we can use more sophisticated algorithms, such as divide and conquer, to reduce this time complexity significantly to O(n log n).

Imagine trying to figure out who is the closest friend to you from a large party. A brute force approach would involve asking each person about their proximity to everyone else until you find the closest. This could take a lot of time, especially if there are many partygoers. However, if you grouped friends by their conversations or locations (like divide and conquer), you could quickly narrow down who is closest without needing to ask everyone individually.

--