This paper investigates the circular retrieval problem and the k-nearest neighbor problem, for sets of n points in the Euclidean plane. Two similar data structures each solve both problems. A deterministic structure uses space O(n(log n log log n)2), and a probabilistic structure uses space O(n log2 n). For both problems, these two structures answer a query that returns k points in O(k + log n) time.
ASJC Scopus subject areas