Maintaining the minimal distance of a point set in polylogarithmic time

Abstract

A dynamic data structure is given that maintains the minimal distance of a set of n points in k-dimensional space in O((log n)^{k+2}) amortized time per update. The size of data structure is bounded by O(n(log n)^{k}). Distances are measured in an arbitrary Minkowski L_{t}-metric, where 1\leq t\leq\infty. This is the first dynamic data structure that maintains the minimal distance in polylogarithmic time, when arbitrary updates are performed.