The Well-Separated Pair Decomposition and Its Applications

Computational geometry is concerned with the design and analysis of algorithms that solve problems on geometric data in ℝ ^d , in which the dimension d is a constant. A large part of the field has been devoted to problems that involve distances determined by pairs of points in a given point set. Given a set S of n points in ℝ ^d , we may wish to compute a pair p, q of distinct points in S whose distance is minimum, the k smallest distances among the ( n 2 ) https://s3-euw1-ap-pe-df-pch-content-public-u.s3.eu-west-1.amazonaws.com/9781351235426/021cf6c0-a3fa-48d9-836a-fa4830c7d2d0/content/equ_0187.tif"/> pairwise distances, the nearest neighbor of each point of S, or the minimum spanning tree of S. Most problems of this type can be rephrased as a graph problem on the complete Euclidean graph on S, in which each edge pq has a weight being the Euclidean distance |pq| between p and q. As the number of edges in this graph is Θ(n ²), many problems involving pairwise distances can trivially be solved in O(n ²) time. Even though the complete Euclidean graph has size Θ(n ²), it can be represented in Θ(n) space: It is clearly sufficient to only store the points of S, because the weight of any edge can be computed in O(1) time. This leads to the question whether distance problems can be solved in subquadratic time, possibly at the cost of obtaining an approximate solution. For many of these problems, subquadratic algorithms have indeed been designed; see for example, the books by Preparata and Shamos [1] and de Berg et al. [2], and the survey papers by Bern and Eppstein [3], Eppstein [4], and Smid [5]. Most of these algorithms, however, are tailored to the problem at hand.