Thinning to improve two-sample discrepancy

The discrepancy between two independent samples $X_1,\dots ,X_n$ and $Y_1,\dots ,Y_n$ drawn from the same distribution on ${\mathbb{R}}^d$ typically has order $O(\sqrt{n})$ even in one dimension. We give a simple online algorithm that reduces the discrepancy to $O({\log }^{2d}n)$ by discarding a small fraction of the points.