Computing the Minimum Diameter for Moving Points: An Exact Implementation using Parametric Search
Jörg Schwerdt, Michiel Smid, Stefan Schirra · 1997
p(t) and q(t) at time t by d(p(t); q(t)). We dene the diameter D(t), at time t, of a set S of moving points as the largest Euclidean distance among all pairs of points at time t. To be more precise D(t) = maxfd(p(t); q(t)) : p; q 2 Sg: Problem 1.1 (The diameter problem for moving points) We are given a set of n points in the plane that are moving at constant but possibly dierent velocities. We want to compute the time t at which the diameter D(t ) is minimum. 2 Moving Poin