turkmath.org

We study the number of copies of a given digraph in k nearest neighbor (kNN) digraph of the data from a random point process in $\mathbb{R}^d$. Based on the asymptotic theory for functionals of point sets under homogeneous Poisson process (HPP) and uniform binomial process, we provide a general result for the asymptotic behavior of subdigraph counts and as corollaries, we obtain asymptotic results for the number of vertices with fixed indegree, the number of shared kNN pairs and the number of reflexive kNN's in a kNN digraph. Moreover, we use the method to analyze kNN contingency tables for several classes under HPP.