K. L. Clarkson. Algorithms for the Minimum Diameter of Moving Points and for the Discrete 1-center Problem. Submitted for publication.
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.