Publication
Information Processing Letters
Paper

Deferred data structure for the nearest neighbor problem

View publication

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.

Date

08 Nov 1991

Publication

Information Processing Letters

Authors

Topics

Share