Joel L. Wolf, Mark S. Squillante, et al.
IEEE Transactions on Knowledge and Data Engineering
Paper
Deferred data structure for the nearest neighbor problem
Abstract
Let S be a set of n points in the plane. We show how to process, on-line, a sequence of r point queries for computing their nearest neighbors in S, in time Θ((n + r) log min(n, r)). This settles an open problem posed by Karp. Motwani and Raghavan. © 1991.
Related
J.P. Locquet, J. Perret, et al.
SPIE Optical Science, Engineering, and Instrumentation 1998
Conference paper
Automatic taxonomy generation: Issues and possibilities
Raghu Krishnapuram, Krishna Kummamuru
IFSA 2003
Marshall W. Bern, Howard J. Karloff, et al.
Theoretical Computer Science