返回Google圖書搜尋

New Algorithms for Near Neighbor Searching

出版	Brown University, Department of Computer Science, 1983
URL	http://books.google.com.hk/books?id=ivrxNwAACAAJ&hl=&source=gbs_api

註釋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).