I have two sets of points, $X$ and $Y$, which are finite and disjoint. I want to compute the distance between them defined by: $$d(X,Y)= \frac{\sum_{x \in X} \|x-Y\| + \sum_{y \in Y} \|y-X\|}{|x|+|y|} $$ where $\|x-Y\|$ represents the distance between the point $x$ in $X$ to its closest point in $Y$, and $|x|$, $|y|$ are the cardinalities of $X$ and $Y$ respectively.
Since both sets are large, the above formula is computationally expensive. How can I calculate it or bound it efficiently?
Let $d(x,Y):=\min\{\|x-y\|\colon y\in Y\}$ and $d(y,X):=\min\{\|y-x\|\colon x\in X\}$. Then $$d(X,Y)=(1-w)d_X(Y)+wd_Y(X),$$ where $$w:=\frac{|Y|}{|X|+|Y|},$$ $|X|$ and $|Y|$ are the cardinalities of $X$ and $Y$, respectively, and $$d_X(Y):=\frac1{|X|}\sum_{x\in X}d(x,Y)\quad\text{and}\quad d_Y(X):=\frac1{|Y|}\sum_{y\in Y}d(y,X)$$ are the average distances from $X$ to $Y$ and from $Y$ to $X$, respectively.
Let $X_1$ and $Y_1$ be (say random) subsets of $X$ and $Y$, respectively, of large but not overly large sizes. Then, obviously, $d(x,Y)\le d(x,Y_1)$ for all $x$ and hence $d_X(Y)\le d_X(Y_1)$. Similarly, $d_Y(X)\le d_Y(X_1)$. So, $$d(X,Y)\le(1-w)d_X(Y_1)+wd_Y(X_1).$$ One could also take some large enough (say random) subsets $X_2$ and $Y_2$ of $X$ and $Y$ such that $w_2:=\frac{|Y_2|}{|X_2|+|Y_2|}\approx w$ and thus get a presumably upper estimate $$(1-w_2)d_{X_2}(Y_1)+w_2d_{Y_2}(X_1)$$ of $d(X,Y)$.
These methods should work well if $X$ and $Y$ are well enough separated from each other on an average and if $w$ is known or can be estimated well enough.
