New Algorithms for Near Neighbor Searching.
Bernard Chazelle, Franco P. Preparata · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign) · 1983
NOTES 19. KEY WO ROS (Continue on reveree aide if neceea ery and identify by block number) Geometric searching, near-neighbor search, Voronoi diagrams, bounded radius search, filtering search, efficient algorithms A B S TR A C T (Continue on reverae aide If neceaaery and identify by block number)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 qnarv nf form (q,k), with 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 auerv nf 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.