The Closest Pair of Points Problem

Now that we know what characterizes a divide and conquer algorithm and are familiar with the master method to derive bounds from recurrences, let's look at a problem solvable by a divide and conquer approach.

The problem we will be looking at is the problem of finding the closest pair of points on a plane. We are given an array of n points in the plane, and we want to find out the closest pair of points in this array. Recall that the distance between two points, p and q, is given by the following:

Our first approach may be to compute the distance between each pair and return the smallest, for a runtime complexity ...

Get Beginning Java Data Structures and Algorithms now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.