Key points are not available for this paper at this time.
In this paper, we give results relevant to sequential and distributed dynamic data structures for finding nearest neighbors in growth-restricted metrics. Our sequential data structure uses linear space, and requires O(log n) queries in expecation and O(log n) queries for lookups with high probability. This improves the results of Karger and Ruhl 4, whose data structure uses O(n log n) space with comparable expected time bounds. This also improves on the time bound of a load-balanced version of algorithm (for dynamic networks) presented in 3.
Hildrum et al. (Sun,) studied this question.