On nearest-neighbor graphs

被引：129

作者：

Eppstein, D

Paterson, MS

Yao, FF

机构：

[1] UNIV WARWICK, DEPT COMP SCI, COVENTRY CV4 7AL, W MIDLANDS, ENGLAND

[2] XEROX CORP, PALO ALTO RES CTR, PALO ALTO, CA 94304 USA

来源：

DISCRETE & COMPUTATIONAL GEOMETRY | 1997年 / 17卷 / 03期

关键词：

D O I：

10.1007/PL00009293

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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.

引用

页码：263 / 282

页数：20

共 16 条

[1] Alon N., 1992, PROBABILISTIC METHOD
[2] [Anonymous], P 7 ANN S COMP GEOM
[3] 2 PROBABILISTIC RESULTS ON RECTILINEAR STEINER TREES
BERN, MW
[J]. ALGORITHMICA, 1988, 3 (02) : 191 - 204
[4] A VECTORIZED NEAR NEIGHBORS ALGORITHM OF ORDER N USING A MONOTONIC LOGICAL GRID
BORIS, J
[J]. JOURNAL OF COMPUTATIONAL PHYSICS, 1986, 66 (01) : 1 - 20
[5] Callahan P. B., 1992, Proceedings of the Twenty-Fourth Annual ACM Symposium on the Theory of Computing, P546, DOI 10.1145/129712.129766
[6] CALLAHAN PB, 1993, AN S FDN CO, P332
[7] Clarkson Kenneth L., 1983, P 24 ANN IEEE S FDN, P226, DOI [DOI 10.1109/SFCS.1983.16, 10.1109/ SFCS.1983.16, 10.1109/SFCS.1983.16]
[8] Conway JH., 1988, SPHERE PACKINGS LATT, DOI 10.1007/978-1-4757-2016-7
[9] THE EXPECTED SIZE OF SOME GRAPHS IN COMPUTATIONAL GEOMETRY
DEVROYE, L
[J]. COMPUTERS & MATHEMATICS WITH APPLICATIONS, 1988, 15 (01) : 53 - 64
[10] Algorithms for proximity problems in higher dimensions
Dickerson, MT
Eppstein, D
[J]. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 1996, 5 (05): : 277 - 291

← 1 2 →