K-nearest-neighbor clustering and percolation theory

Shang-Hua Teng; Frances F. Yao

doi:10.1007/s00453-007-9040-7

K-nearest-neighbor clustering and percolation theory

Shang-Hua Teng
, Frances F. Yao

Department of Computer Science

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

14 Citations (Scopus)

Abstract

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 ₂ 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 ₂=3. We also obtain similar results for finite random point sets. © 2007 Springer Science+Business Media, LLC.

Original language	English
Pages (from-to)	192-211
Journal	Algorithmica (New York)
Volume	49
Issue number	3
DOIs	https://doi.org/10.1007/s00453-007-9040-7
Publication status	Published - Nov 2007

Research Keywords

Clustering
Nearest neighbor graph
Percolation
Random point set

Access Output

10.1007/s00453-007-9040-7

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{697755aa699c40e2bc9db6fa1003c3be,

title = "K-nearest-neighbor clustering and percolation theory",

abstract = "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. {\textcopyright} 2007 Springer Science+Business Media, LLC.",

keywords = "Clustering, Nearest neighbor graph, Percolation, Random point set",

author = "Shang-Hua Teng and Yao, \{Frances F.\}",

year = "2007",

month = nov,

doi = "10.1007/s00453-007-9040-7",

language = "English",

volume = "49",

pages = "192--211",

journal = "Algorithmica (New York)",

issn = "0178-4617",

publisher = "Springer New York",

number = "3",

}

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 - https://www.scopus.com/pages/publications/35348814473

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

SN - 0178-4617

VL - 49

SP - 192

EP - 211

JO - Algorithmica (New York)

JF - Algorithmica (New York)

IS - 3

ER -

K-nearest-neighbor clustering and percolation theory

Abstract

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this