MAINTAINING THE MINIMAL DISTANCE OF A POINT SET IN POLYLOGARITHMIC TIME

A dynamic data structure is given that maintains the minimal distance in a set of n points in k-dimensional space in O((log n)k log log n) amortized time per update. The size of the data structure is bounded by O(n(log n)k). Distances are measured in the Minkowski L(t)-metric, where 1 less-than-or-equal-to t less-than-or-equal-to infinity. This is the first dynamic data structure that maintains the minimal distance in polylogarithmic time for fully on-line updates.