An optimal algorithm for the on-line closest-pair problem
Christian J. Schwarz, Michiel Smid, Jack Scott Snoeyink · 1992
We give an algorithm that computes the closest pair in a set of n points in k- dimensional space on-line, in O(n log n) time. The algorithm only uses algebraic functions and, therefore, is optimal. The algorithm maintains a hierarchical subdivision of k-space into hyperrectangles, which is stored in a binary tree. Centroids are used to maintain a balanced decomposition of this tree. 1 Introduction The closest pair problem is one of the classical problems in computational geometry. In this problem, we have to compute the closest pair---or its distance---in a set of n points in k-dimensional space. Distances are measured in an arbitrary, but fixed, L t -metric. Let p = (p 1 ; : : : ; p k ) and q = (q 1 ; : : : ; q k ) be two points in k-dimensional space. Then the L t -distance d t (p; q) between p and q is defined by d t (p; q) := / k X i=1 jp i \\Gamma q i j t !1=t ; if 1 t ! 1, and for t = 1, it is defined by d1 (p; q) := max 1ik jp i \\Gamma q i j: We observe, as many o...