Karlsson, R. G. and Munro, J. I. (1986). Proximity on a Grid under L1 and L1 Metrics. Technical Report LiTH-IDA-R-86-27, Department of Computer and Information Science, Linköping University, Sweden. A preliminary version appeared in 2nd Symposium on Theoretical Aspects of Computer Science, 1985, Springer-Verlag, LNCS, 182, 187-196. (bibtex),
Abstract: We introduce a trie based data structure to support nearest neighbor queries, under the L1 and L norms, on a discrete u5 by u grid. It is shown that a static structure, occupying O(n) space to store n points, can be searched in O(loglog u) time. Dynamic and semidynamic (insertions permitted) are also introduced. The dynamic form supports queries and updates in O(log3/2u) time and the semidynamic, in O(log u) time. Both use O(nlog u) space and can be extended to higher dimensions.
CS Dept TR Overview