3
$\begingroup$

The closest pair problem is the famous problem of finding out the closest pair of points given an arbitrary set of points on a plane. This problem has a divide and conquer algorithm and often is used in algorithms classes to illustrate the divide and conquer paradigm.

I also intend to do the same, but I would like to begin with some comments on why this algorithm is useful. Are there any interesting examples I can use here? A google search reveals nothing.

This is for an introductory algorithms course, and the audience is not expected to be an expert on this topic and has a mediocre level of mathematical maturity.

$\endgroup$
  • 1
    $\begingroup$ Introducing neighbors to each other? Picking up stranded people in a disaster? $\endgroup$ – Ellen Spertus Jul 31 at 22:13
4
$\begingroup$

Rosen, Discrete Mathematics and its Applications, Sec. 8.3, says:

This problem arises in many applications such as determining the closest pair of airplanes in the air space at a particular altitude being managed by an air traffic controller.

$\endgroup$
  • 2
    $\begingroup$ Welcome to CSE Stack Exchange. Great first answer! $\endgroup$ – Ellen Spertus Aug 3 at 22:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.