A fast algorithm for two-dimensional Kolmogorov-Smirnov two sample tests

By using the brute force algorithm, the application of the two-dimensional two-sample Kolmogorov-Smirnov test can be prohibitively computationally expensive. Thus a fast algorithm for computing the two-sample Kolmogorov-Smirnov test statistic is proposed to alleviate this problem. The newly proposed algorithm is O(n) times more efficient than the brute force algorithm, where n is the sum of the two sample sizes. The proposed algorithm is parallel and can be generalized to higher dimensional spaces.