Closest pair of points

Another example is an algorithm to find the closest pair of points located on the two-dimensional surface. It is an interesting algorithmic problem that can be solved using the divide-and-conquer paradigm.

Each point is represented by x and y coordinates, with values starting from (0, 0) in the top-left corner of the surface. To find the closest pair of points, you first sort all points according to the x coordinate, as shown in the following diagrams, marked from A to N:

Figure 9.3 – Diagrams of the algorithm to find the closest pair of points

Then, you divide the surface into two halves. You can do this by calculating half of the points count, namely 7 in our example, and taking the first 7 points as the left half and the next 7 points as the right half.

Here is a task for recursion, so you recursively find the closest points in both halves and store data as rl (points D and E) and rr (points I and K). You choose the...