New Algorithms for Near Neighbor Searching.
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 0(n to the 1 plus epsilon power) space, 0(k + 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 0(k log squared n) query time, using only 0(n 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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1983
- Accession Number
- ADA142404
Entities
People
- Bernard Chazelle
- Franco P. Preparata
Organizations
- University of Illinois Urbana–Champaign