Finding k farthest pairs and k closest/farthest bichromatic pairs for points in the plane

摘要

We study the problem of enumerating k farthest pairs for n points in the plane and the problems of enumerating k closest/farthest bichromatic pairs of n red and n blue points in the plane. We propose a new technique for geometric enumeration problems which iteratively reduces the search space by a half and provides efficient algorithms. As applications of this technique, we develop algorithms, using higher order Voronoi diagrams, for the above problems, which run in O(min{n2, n log n + k4/3 log n/log1/3 k}) time and O(n+k4/3/(log k)1/3+k log n) space. Since, to the authors' knowledge, no nontrivial algorithms have been known for these problems, our algorithms are currently fastest when k=o(n3/2).