Studies of galaxy clustering through the use of binary tree hierarchies. I. Multipoint correlation functions

A method is presented for the evaluation of multipoint correlation functions employing the analysis of the structure of a "binary tree" which spans the particular set of galaxies under consideration. A recursive center-of-mass transformation is used and a binary tree data structure is compiled. For a large number of particles, N, the computational expense for constructing the tree increases as N log N. In a similar way, the m-point correlation functions are also determined by recursively scanning the nodes of the tree and binning the m-tuplets discovered by the scan. It thus becomes possible to obtain the same N log N functional form for computational expense for general m-point correlation functions versus a cost function of order N^m by the direct counting of m-tuplets. Moreover, it is found that the scanning processes are accelerated if the galaxy set of interest possesses any sort of clustering. If the limits of the counting bins are also relaxed, still further increases in speed are achieved, with little loss of precision in the determination of the correlation functions. A variety of artificial data sets and observed galaxy catalogs have been examined with this approach. Gains of more than two orders of magnitude in computational speed are attained over that possible by direct counting of m-tuplets. This permits the examination of much larger data sets or of higher-order correlations than has been possible thus far. The details of this technique are described here, with the statistical results from these studies to be presented in a subsequent paper.