Maintaining the minimal distance of a point set in polylogarithmic time |
| |
Authors: | Michiel Smid |
| |
Institution: | (1) Max-Planck-Institut für Informatik, W-6600 Saarbrücken, Federal Republic of Germany |
| |
Abstract: | 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.This work was supported by the ESPRIT II Basic Research Actions Program, under Contract No. 3075 (project ALCOM). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|