Clustering of random points in two dimensions

Abstract

Let (x1,yl),(x2,y2),...,(xN,yN) be N points randomly drawn from the unit square. DefineE(n∣N; u,v) as the event: there exists a subrectangle of the unit square, with sides of length u and v oriented parallel to the sides ofthe square (x- and y-axes, respectively), that contains at least n out of the N points. We seek the probability P(n∣N; u, v) of the event E(n∣N; u, v). If either u or v is unity, the problem is at once equivalent to a one-dimensional problem treated previously. Abbreviate P(n∣N; u, 1) to P(nIN; u). A determination of P(N∣N; u) is given by Burnside (1928, p. 22); of P(2∣N; u) by Parzen (1960, p. 304); and of P(n∣N; u) for n ⩾ 1/2N, by Naus (1963, p. 37). Scan the unit square with a subrectangle, r, with sides of length u and voriented parallel to the sides of the square. Eggleton & Kermack (1944, p. 104) define an n/r cluster as any position ofthe subrectangle r in which it contains n points. Eggleton & Kermack (1944) and Mack (1950) seek—for two definitions of ‘equivalent’ —the expected number of non-equivalent n/r clusters. For both Eggleton & Kermack's and Mack's definition of cluster, P(n∣N; u, v) is the probability of at least one cluster of at least n points. In addition, since there can be only one unique cluster of all the points, P(N∣N; u,v) is the expected number of non-equivalent N /r clusters. This paper derives lower and upper bounds to P(n∣N; u,v) that converge as u and v approach zero. Section I presents and applies easily derived upper and lower bounds for P(n∣N; u, v) that do not so converge. Section 2 finds an upper bound that converges to the ‘easy’ lower bound.