On nearest-neighbor graphs

On nearest-neighbor graphs

0.00 Avg rating0 Votes
Article ID: iaor1998880
Country: United States
Volume: 17
Issue: 3
Start Page Number: 263
End Page Number: 282
Publication Date: Apr 1997
Journal: Discrete and Computational Geometry
Authors: , ,
Keywords: statistics: multivariate
Abstract:

The ‘nearest-neighbor’ relation, or more generally the ‘k-nearest-neighbors’ relation, defined for a set of points in a metric space, has found many uses in computational geometry and clustering analysis, yet surprisingly little is known about some of its basic properties. In this paper we consider some natural questions that are motivated by geometric embedding problems. We derive bounds on the relationship between size and depth for the components of a nearest-neighbor graph and prove some probabilistic properties of the k-nearest-neighbors graph for a random set of points.

Reviews

Required fields are marked *. Your email address will not be published.