A RELIABLE RANDOMIZED ALGORITHM FOR THE CLOSEST-PAIR PROBLEM

The following two computational problems are studied: Duplicate groupi ng: Assume that n items are given, each of which is labeled by an inte ger key from the set {0,...,U -1}. Store the items in an array of size n such that items with the same key occupy a contiguous segment of th e array.Closest pair: Assume that a multiset of n points in the d-dime nsional Euclidean space is given, where d greater than or equal to 1 i s a fixed integer. Each point is represented as a d-tuple of integers in the range (0,..., U -1)(or of arbitrary real numbers). Find a close st pair, i.e., a pair of points whose distance is minimal over all suc h pairs.