An efficient k nearest neighbors searching algorithm for a query line

摘要

We present an algorithm for finding k nearest neighbors of a given query line among a set of n points distributed arbitrarily on a two-dimensional plane. Our algorithm requires O(n(2)) time and O(n(2)/logn) space to preprocess the given set of points, and it answers the query for a given line in O(k + log n) time, where k may also be an input at the query time. Almost a similar technique works for finding k farthest neighbors of a query line, keeping the time and space complexities invariant. We also show that if k is known at the time of preprocessing, the time and space complexities for the preprocessing can be reduced keeping the query times unchanged. (C) 2002 Elsevier Science B.V. All rights reserved. [References: 18]