MAINTAINING THE MINIMAL DISTANCE OF A POINT SET IN POLYLOGARITHMIC TIME

被引：11

作者：

SMID, M

机构：

[1] Max-Planck-Institut für Informatik, Saarbrücken

来源：

DISCRETE & COMPUTATIONAL GEOMETRY | 1992年 / 7卷 / 04期

关键词：

D O I：

10.1007/BF02187852

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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.

引用

页码：415 / 431

页数：17

共 15 条

[1] A LINEAR-TIME ALGORITHM FOR COMPUTING THE VORONOI DIAGRAM OF A CONVEX POLYGON [J].