Deferred data structure for the nearest neighbor problem

Alok Aggarwal; Prabhakar Raghavan

doi:10.1016/0020-0190(91)90164-D

Information Processing Letters

Paper

08 Nov 1991

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.

Conference paper