13.7.1. Initial Sorting Phase

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. (Refer Slide Time: 00:11)

In this section, we are introduced to a geometric problem where we need to find the closest pair of points from a given set. This problem becomes particularly relevant in scenarios like video games where determining proximity between objects is crucial for gameplay.

Imagine playing a video game where there are several characters on the screen, and you need to identify which two characters are closest to each other. This problem can be visualized as finding two points on a graph that are nearest to one another.

So, recall that at the beginning of this set of lectures to motivate the need for more efficient algorithms, you consider the example of the video game, if there are several objects on the screen and you might want to find it at any given point, the closest pair of objects among them. So, for this again 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.

The naive approach for finding the closest pair involves calculating the distance between every possible pair of points. If there are 'n' points, this results in 'n choose 2' calculations, which translates to O(n²) time complexity—making it inefficient for a large number of points.

Think of a high school reunion where every attendee wants to find the person they were closest friends with. If there are 100 attendees, each person would need to try bonding with every other attendee, leading to 4,950 interactions! This approach quickly becomes unwieldy.

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.

Unlike the naive method, the divide and conquer strategy significantly reduces the number of calculations. By breaking the problem down into smaller parts, specifically separating points into two halves and processing each half recursively, we can solve it in O(n log n) time.

This approach is like organizing a large seminar where instead of having everyone ask questions one by one, you divide participants into smaller groups that discuss and then share the best questions. This way, you gather the most relevant queries more efficiently.

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 Pythagoras used formula.

In this scenario, each point is represented in a two-dimensional space using x and y coordinates. The distance between any two points can be calculated using the Pythagorean theorem, which states that the distance is the square root of the sum of the squared differences of their coordinates.

Imagine a map where every location is marked with its coordinates. The method of calculating the distance between any two places uses the same principles as finding the shortest path in a straight line from one point to another.

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, we have a bunch of points and we want to find the closest point.

When dealing with one-dimensional points, the closest pair can be easily found by sorting the points and then simply checking the distance between adjacent points. Sorting helps to identify the nearest distances without needing to calculate all possible pairs.

Think of standing in a straight line with friends. If you wanted to know who is the closest friend to you, you would only need to look at the person directly to your left and right instead of everyone in the line.

So, it two dimensions if we are going to use divide and conquer, we need to way of separating the points into two groups, a roughly equal size or a hopefully exactly equal size. So, a natural way is this is the geometric problem is to separate them based on their positions.

To efficiently apply the divide and conquer strategy in two dimensions, we first split the set of points into two roughly equal halves using a vertical line. The goal is to ensure that each half contains an equal number of points, allowing for an organized approach to solving the problem.

Consider a traffic analyst examining vehicles on a highway during rush hour. They may divide traffic into two lanes (left and right) to better manage and analyze both groups separately.

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 we can find the closest pairs within each half, we must also check pairs that cross the dividing line, as the closest points might be positioned on opposite sides of the split line. This necessitates additional computation to ensure accuracy.

Think about two friends standing on either side of a fence. Even though they are separated, they might still be standing closely relative to each other. We cannot ignore their proximity just because they fall on different sides.

--