Closest Pair in the Plane with (2,4)-trees

Web Page and Applets by Sam Sanjabi
Presented to Prof. Godfried Toussaint

1 Introduction

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