AnO(n logn) algorithm for the all-nearest-neighbors Problem |
| |
Authors: | Pravin M Vaidya |
| |
Institution: | (1) Department of Computer Science, University of Illinois at Urbana-Champaign, 61801 Urbana, IL, USA |
| |
Abstract: | Given a setV ofn points ink-dimensional space, and anL
q
-metric (Minkowski metric), the all-nearest-neighbors problem is defined as follows: for each pointp inV, find all those points inV–{p} that are closest top under the distance metricL
q
. We give anO(n logn) algorithm for the all-nearest-neighbors problem, for fixed dimensionk and fixed metricL
q
. Since there is an (n logn) lower bound, in the algebraic decision-tree model of computation, on the time complexity of any algorithm that solves the all-nearest-neighbors problem (fork=1), the running time of our algorithm is optimal up to a constant factor.This research was supported by a fellowship from the Shell Foundation. The author is currently at AT&T Bell Laboratories, Murray Hill, New Jersey, USA. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|