@techreport{R-86-27,
TITLE = {Proximity on a Grid under L1 and L1 Metrics},
AUTHOR = {Rolf G. Karlsson and J. Ian Munro },
YEAR = {1986},
NUMBER = {R-86-27},
INSTITUTION = ida,
ADDRESS = idaaddr,
ABSTRACTURL = {/publications/cgi-bin/tr-fetch.pl?r-86-27+abstr},
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.},
IDANR = {LiTH-IDA-R-86-27},
NOTE = {A preliminary version appeared in 2nd Symposium on Theoretical Aspects of Computer Science, 1985, Springer-Verlag, LNCS, 182, 187-196}