  This paper introduces a new way to calculate distance-based statistics,
particularly when the data are multivariate. The main idea is to pre-calculate
the optimal projection directions given the variable dimension, and to project
multidimensional variables onto these pre-specified projection directions; by
subsequently utilizing the fast algorithm that is developed in Huo and
Sz\'ekely [2016] for the univariate variables, the computational complexity can
be improved from $O(m^2)$ to $O(n m \cdot \mbox{log}(m))$, where $n$ is the
number of projection directions and $m$ is the sample size. When $n \ll
m/\log(m)$, computational savings can be achieved. The key challenge is how to
find the optimal pre-specified projection directions. This can be obtained by
minimizing the worse-case difference between the true distance and the
approximated distance, which can be formulated as a nonconvex optimization
problem in a general setting. In this paper, we show that the exact solution of
the nonconvex optimization problem can be derived in two special cases: the
dimension of the data is equal to either $2$ or the number of projection
directions. In the generic settings, we propose an algorithm to find some
approximate solutions. Simulations confirm the advantage of our method, in
comparison with the pure Monte Carlo approach, in which the directions are
randomly selected rather than pre-calculated.
