Accession Number:

ADA142404

Title:

New Algorithms for Near Neighbor Searching.

Descriptive Note:

Technical rept.,

Corporate Author:

ILLINOIS UNIV AT URBANA APPLIED COMPUTATION THEORY GROUP

Personal Author(s):

Report Date:

1983-09-01

Pagination or Media Count:

23.0

Abstract:

This paper proposes a new technique for solving near neighbor problems in the plane. We illustrate our method on the following two problems 1. k-Nearest neighbor Given a set S of n points in the plane and a query of the form q,k, with a q a query point and k a positive integer, report the k points of S closest to q. 2. Circular Range Search Given a set S of n points in the plane and a query of the form q,d, with q a query point and d a positive real number, report all the points of S that lie inside the circle of radius d, centered at q. Our main results include 0n to the 1 plus epsilon power space, 0k log n query time algorithms for solving each of these problems k denotes the size of the output. We also show that it is possible to solve either problem in 0k log squared n query time, using only 0n log n space. These results constitute significant improvements over previous methods, in particular regarding the circular range search problem, which had previously defied efficient solutions. Author

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE