Figure 1
(left) Running times with respect to the number of points is shown. (right) The relation between the total number of well-separated pairs and the number of points is depicted with boxes. The compression ratio, i.e., the total number of wellseparated pairs divided by the total number of pairwise distances n·(n–1)/2, is depicted with lines.
Figure 2
A simple example of a WSPD for eight blue points in the plane computed with separation constant s = 2. The WSPD algorithm computed ten well-separated pairs, denoted as green dashed lines. Thus, all pairwise distances between points in different red rectangles will be approximated with corresponding green dashed lines.