private boolean prune(double[] center, double[] radius, double[][] centroids, int bestIndex, int testIndex) {
        if (bestIndex == testIndex) {
            return false;
        }

        int d = centroids[0].length;

        double[] best = centroids[bestIndex];
        double[] test = centroids[testIndex];
        double lhs = 0.0, rhs = 0.0;
        for (int i = 0; i < d; i++) {
            double diff = test[i] - best[i];
            lhs += diff * diff;
            if (diff > 0) {
                rhs += (center[i] + radius[i] - best[i]) * diff;
            } else {
                rhs += (center[i] - radius[i] - best[i]) * diff;
            }
        }

        return (lhs >= 2 * rhs);
    }
private boolean prune ( double [ ] center , double [ ] radius , double [ ] [ ] centroids , int bestIndex , int testIndex ) { if ( bestIndex == testIndex ) { return false ; } int d = centroids [ 0 ] . length ; double [ ] best = centroids [ bestIndex ] ; double [ ] test = centroids [ testIndex ] ; double lhs = 0.0 , rhs = 0.0 ; for ( int i = 0 ; i < d ; i ++ ) { double diff = test [ i ] - best [ i ] ; lhs += diff * diff ; if ( diff > 0 ) { rhs += ( center [ i ] + radius [ i ] - best [ i ] ) * diff ; } else { rhs += ( center [ i ] - radius [ i ] - best [ i ] ) * diff ; } } return ( lhs >= 2 * rhs ) ; }
Determines whether every point in the box is closer to centroids[bestIndex] than to
centroids[testIndex].

If x is a point, c_0 = centroids[bestIndex], c = centroids[testIndex], then:
(x-c).(x-c) < (x-c_0).(x-c_0)
<=> (c-c_0).(c-c_0) < 2(x-c_0).(c-c_0)

The right-hand side is maximized for a vertex of the box where for each
dimension, we choose the low or high value based on the sign of x-c_0 in
that dimension.