Maintaining the minimal distance of a point set in polylogarithmic time
Michiel Smid · Symposium on Discrete Algorithms · 1991
A dynamic data structure is given that maintains the minimal distance in a set ofn points ink-dimensional space inO((logn) k log logn) amortized time per update. The size of the data structure is bounded byO(n(logn) k ). Distances are measured in the MinkowskiL t -metric, where 1 ≤t ≤ ∞. This is the first dynamic data structure that maintains the minimal distance in polylogarithmic time for fully on-line updates.