On nearest-neighbor graphs

被引：128
|
作者：
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
相关论文
共 50 条
  • [21] WEIGHTED NEAREST-NEIGHBOR ANALYSIS
    SCHWARZBACH, E
    BIOMETRICS, 1985, 41 (04) : 1088 - 1088
  • [22] Coresets for the nearest-neighbor rule
    Department of Computer Science, University of Maryland, College Park
    MD, United States
    不详
    MD, United States
    Leibniz Int. Proc. Informatics, LIPIcs,
  • [23] FASTER NEAREST-NEIGHBOR CALCULATIONS
    BATCHELOR, BG
    ELECTRONICS LETTERS, 1977, 13 (10) : 304 - 306
  • [24] Nearest-neighbor variance estimation (NNVE): Robust covariance estimation via nearest-neighbor cleaning
    Wang, N
    Raftery, AE
    JOURNAL OF THE AMERICAN STATISTICAL ASSOCIATION, 2002, 97 (460) : 994 - 1006
  • [25] NEAREST-NEIGHBOR MULTICHANNEL FILTER
    PLATANIOTIS, KN
    ANDROUTSOS, D
    SRI, V
    VENETSANOPOULOS, AN
    ELECTRONICS LETTERS, 1995, 31 (22) : 1910 - 1911
  • [26] CHOICE OF NEIGHBOR ORDER IN NEAREST-NEIGHBOR CLASSIFICATION
    Hall, Peter
    Park, Byeong U.
    Samworth, Richard J.
    ANNALS OF STATISTICS, 2008, 36 (05): : 2135 - 2152
  • [27] NEAREST-NEIGHBOR MAPPING OF FINITE-ELEMENT GRAPHS ONTO PROCESSOR MESHES
    SADAYAPPAN, P
    ERCAL, F
    IEEE TRANSACTIONS ON COMPUTERS, 1987, 36 (12) : 1408 - 1424
  • [28] Derivation of nearest-neighbor properties from oligomers: Consequences of nearest-neighbor absences and treatment of ends.
    Gray, DM
    BIOPHYSICAL JOURNAL, 1997, 72 (02) : WP412 - WP412
  • [29] Following Surgical Trajectories with Concentric Tube Robots via Nearest-Neighbor Graphs
    Niyaz, Sherdil
    Kuntz, Alan
    Salzman, Oren
    Alterovitz, Ron
    Srinivasa, Siddhartha
    PROCEEDINGS OF THE 2018 INTERNATIONAL SYMPOSIUM ON EXPERIMENTAL ROBOTICS, 2020, 11 : 3 - 13
  • [30] NEAREST-NEIGHBOR MAPPING OF FINITE ELEMENT GRAPHS ONTO PROCESSOR MESHES.
    Sadayappan, Ponnuswamy
    Ercal, Fikret
    IEEE Transactions on Computers, 1987, C-36 (12) : 1408 - 1424
12345