On nearest-neighbor graphs
On nearest-neighbor graphs
复制标题
DOI：
10.1007/pl00009293
复制
发表时间：
1997-04-01
影响因子：
0.8
通讯作者：
Yao, FF
中科院分区：
文献类型：
--
作者：
Eppstein, D;Paterson, MS;Yao, FF
最近邻关系，或更一般的k-最近邻关系，定义为度量空间中的一组点，在计算几何和聚类分析中有许多用途，但令人惊讶的是，对它的一些基本性质知之甚少。在本文中，我们考虑一些自然的问题，几何嵌入问题的动机。我们推导出的最近邻图的组件的大小和深度之间的关系的界限，并证明了随机点集的k-最近邻图的一些概率性质。
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.