TY - JOUR
T1 - K-nearest-neighbor clustering and percolation theory
AU - Teng, Shang-Hua
AU - Yao, Frances F.
PY - 2007/11
Y1 - 2007/11
N2 - Let P be a realization of a homogeneous Poisson point process in ℝ
d with density 1. We prove that there exists a constant k
d , 1d d . In particular, we prove that k
2 213. Our analysis establishes and exploits a close connection between the k-nearest neighborhood graphs of a Poisson point set and classical percolation theory. We give simulation results which suggest k
2=3. We also obtain similar results for finite random point sets. © 2007 Springer Science+Business Media, LLC.
AB - Let P be a realization of a homogeneous Poisson point process in ℝ
d with density 1. We prove that there exists a constant k
d , 1d d . In particular, we prove that k
2 213. Our analysis establishes and exploits a close connection between the k-nearest neighborhood graphs of a Poisson point set and classical percolation theory. We give simulation results which suggest k
2=3. We also obtain similar results for finite random point sets. © 2007 Springer Science+Business Media, LLC.
KW - Clustering
KW - Nearest neighbor graph
KW - Percolation
KW - Random point set
UR - http://www.scopus.com/inward/record.url?scp=35348814473&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-35348814473&origin=recordpage
U2 - 10.1007/s00453-007-9040-7
DO - 10.1007/s00453-007-9040-7
M3 - RGC 21 - Publication in refereed journal
VL - 49
SP - 192
EP - 211
JO - Algorithmica (New York)
JF - Algorithmica (New York)
SN - 0178-4617
IS - 3
ER -