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
Descriptors:
Subject Categories:
- Theoretical Mathematics