Web Page and Applets by Sam Sanjabi
Presented to Prof. Godfried Toussaint
The Closest Pair problem consists of finding a pair of points p and q
from a set of n points such that the p and q are at a
minimum distance from each other.
The brute force solution to this problem takes O(n2)
comparisons to check the distance between each possible pair of points.
However, there are faster methods which are presented in this document.
We shall begin by presenting the problem in one-dimension. Upon
generalizing to two dimensions we shall present two different techniques to
efficiently solve the problem: a divide and conquer approach and a plane
sweep algorithm.
At the end of the document, we present an interactive java applet that
demonstrates these techniques. Since a primary structure used to store the
points in these applets is (2-4)-trees, we also present a complete tutorial
on this data structure (complete with its own applet).
Sam Bakhtiar SANJABI
Last modified: Tue Apr 25 08:37:15 EDT 2000