K. L. Clarkson. Algorithms for the Minimum Diameter of Moving Points and for the Discrete 1-center Problem. Submitted for publication.

full paper

Abstract:

Given points moving with constant, but possibly different, velocities, the minimum moving diameter problem is to find the minimum, over all time, of the maximum distance between a pair of points at each moment. This note gives a randomized algorithm requiring O(n log n ) expected time for this problem, in two and three dimensions. Also briefly noted is a randomized O(n log n log log n) expected-time algorithm for the discrete 1-center problem in three dimensions; in this problem, a member p of a set S of points is desired, whose maximum distance to S is minimum over all points of S.