We describe a new randomized data structure, the sparse partition, for solving the dynamic closest-pair problem. Using this data structure the closest pair of a set of n points in D-dimensional space, for any fixed D, can be found in constant time. If a frame containing all the points is known in advance, and if the floor function is available at unit cost, then the data structure supports insertions into and deletions from the set in expected O(log n) time and requires expected O(n) space. This method is more efficient than any deterministic algorithm for solving the problem in dimension D > 1. The data structure can be modified to run in O(log 2 n) expected time per update in the algebraic computation tree model. Even this version is more efficient than the best currently known deterministic algorithm for D > 2. Both results assume that the sequence of updates is not determined in any way by the random choices made by the algorithm.

No abstract available.

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...