Divide-and-conquer in multidimensional space

Abstract

We investigate a divide-and-conquer technique in multidimensional space which decomposes a geometric problem on N points in k dimensions into two problems on N/2 points in k dimensions plus a single problem on N points in k−1 dimension. Special structure of the subproblems is exploited to obtain an algorithm for finding the two closest of N points in 0(N log N) time in any dimension. Related results are discussed, along with some conjectures and unsolved geometric problems.