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 O’Reilly online learning.

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