Before revision:  Kaplan et al. has generalized shallow cuttings to general distance functions, but the size of their version has an extra double logarithmic factor.
After revision:  Kaplan et al. has generalized shallow cuttings to general distance functions, but their shallow cuttings could not be applied to the k nearest neighbors problem. Recently, Kaplan et al. constructed shallow cuttings that are feasible for the k nearest neighbors problem, while the size of their version has an extra double logarithmic factor.