K-nearest-neighbor clustering and percolation theory

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

13 Scopus Citations
Scopus Metrics
View graph of relations

Author(s)

  • Shang-Hua Teng
  • Frances F. Yao

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)192-211
Journal / PublicationAlgorithmica (New York)
Volume49
Issue number3
Publication statusPublished - Nov 2007

Link(s)

DOI

DOI
Check@CityULib
Link to Scopus https://www.scopus.com/record/display.uri?eid=2-s2.0-35348814473&origin=recordpage
Permanent Link https://scholars.cityu.edu.hk/en/publications/publication(697755aa-699c-40e2-bc9d-b6fa1003c3be).html

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. © 2007 Springer Science+Business Media, LLC.

Research Area(s)

  • Clustering, Nearest neighbor graph, Percolation, Random point set

Fingerprint

Publication fingerprints text

100
Constant Mathematics
100
Neighbourhood Mathematics
100
Clustering Mathematics
100
Nearest Neighbor Mathematics
100
Random Point Mathematics
100
Homogeneous Poisson... Mathematics
100
Poisson Point Mathematics
100
Cluster Theory Keyphrases
100
Percolation Theory Keyphrases
100
K-nearest Keyphrases
Full Fingerprint ›

Citation Format(s)

[ RIS ] [ BibTeX ]
K-nearest-neighbor clustering and percolation theory. / Teng, Shang-Hua; Yao, Frances F.
In: Algorithmica (New York), Vol. 49, No. 3, 11.2007, p. 192-211.

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