A set of n points in space naturally defines O(n^2) pairs of
"interactions". When n is large, these quadratically many pairs may
be too large a set to store or compute with directly. Is it possible
to approximate all these interactions using a structure of only linear
size? In this expository talk, we will introduce the concept of a
WELL-SEPARATED PAIR DECOMPOSITION (WSPD) of a set of points. This
important concept was introduced by Callahan and Kosaraju. A WSPD
achieves the goal mentioned above by approximating the O(n^2) pairs
by O(n) pairs of "well-separated" subsets of points.
We will discuss some applications of WSPD's, among them the
construction of EUCLIDEAN SPANNERS. A Euclidean spanner of a set of
points in space is a graph of size O(n) that approximates the complete
Euclidean graph in the sense that, the shortest path between any two
points in the spanner is at most a constant factor longer than the
Euclidean distance between the points. We will also discuss
decomposition of spanners into trees.