An efficient algorithm for the three-dimensional diameter problem
Sergei N. Bespamyatnikh · 1998
We give a deterministic algorithm for computing the diameter of an n-point set in three dimensions with O(n log 2 n) running time. This bound matches the best previous algorithm of Ramos [18]. However, our algorithm applies another technique and is simpler. 1 Introduction We address the well-known diameter problem: The diameter problem. Given a set S of n points in d-dimensional space. Compute the diameter of S, defined as the maximum distance between two points of S. Let diam(S) denote the diameter of set S. In this paper we consider three-dimensional diameter problem. This problem was solved by Clarkson and Shor [7] by a randomized algorithm with optimal expected running time O(n log n). The diameter can be computed in O(n 2 ) time by brute force. Yao solved this problem in O((n log n) 1:8 ) time [20] (in higher dimension d 4 he obtained O(n 2\\Gammaa(d) log 1\\Gammaa(d) n) time, where a(d) = 2 \\Gamma(d+1) ). By computing a structure that allows point location in t...